首页 > 试题广场 >

重要节点

[编程题]重要节点

热度指数：1313 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一张有向图 G(V,E) ，所有的边都是有向边，对于图上的一个点 v ，从 v 出发可以到达的点的集合记为 S_v，特别地， v ∈ S_v，再定义一个点的集合 T_v：从T_v中的任意一个点出发，可以到达点 v ，特别地，v∈T_v简而言之，S_v是 v 能到的点的集合，而 T_v是能到 v 的点的集合。

对于一个点 v ，如果 T_v中的点数严格大于 S_v 中的点数，那么 v 就是一个重要节点，输入一张图，输出图中重要节点的个数

数据范围： $1 \le n,m \le 1000 \$ ， $1 \le u,v \le n \$

输入描述:

第一行输入两个数 n,m ，分别表示点数和边数。
接下来 m 行，每行两个数 u ， v 。表示一条从 u 到 v 的有向边，输入中可能存在重边和自环。

输出描述:

输出一个数，重要节点的个数

示例1

输入

输出

说明

样例解释：重要节点是1，4。

算法知识视频讲解

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, u, v, cnt=0;
    scanf("%d%d", &n, &m);
    vector<int> G[n+1];
    bool C[n+1][n+1] = {false};
    for(int i=0;i<m;i++){
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    int S[n+1]={0}, T[n+1]={0};
    queue<int> q;
    for(int i=1;i<=n;i++){
        q.push(i);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(auto &v: G[u]){
                if(!C[i][v]){
                    C[i][v] = true;
                    S[i]++;
                    T[v]++;
                    q.push(v);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(T[i] > S[i])
            cnt++;
    printf("%d\n", cnt);
    return 0;
}

发表于 2020-09-10 13:01:25 回复(0)

C/C++

Dave_lzw

图正着反着跑一遍

#include <bits/stdc++.h>
using namespace std;
const int AX = 1e3 + 666 ;
int vis[AX] ;
vector<int>G[5][AX] ;
int ans[5] ;
void dfs( int x , int id ) {
	vis[x] = 1 ;
	ans[id] ++ ;
	for( int i = 0 ; i < G[id][x].size() ; i++ ) {
		int y = G[id][x][i] ;
		if( !vis[y] ) dfs( y , id ) ;
	}
}
int main() {
	int n , m ;
	scanf("%d%d",&n,&m);
	int x , y ;
	while( m-- ) {
		scanf("%d%d",&x,&y);
		if( x == y ) continue ;
		G[0][x].push_back(y) ;
		G[1][y].push_back(x) ;
	}
	int res = 0 ;
	for( int i = 1 ; i <= n ; i++ ) {
		ans[0] = 0 ;
		ans[1] = 0 ;
		memset( vis , 0 , sizeof(vis) ) ;
		dfs( i , 0 ) ;
		memset( vis , 0 , sizeof(vis) ) ;
		dfs( i , 1 ) ;
		if( ans[1] > ans[0] ) res ++ ;
	}
	printf("%d\n",res);
	return 0 ;
}

编辑于 2020-04-18 18:43:31 回复(0)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @author wylu
 */
public class Main {
    //arrive[i][j]为true表示从i可以到达j, false则不能
    static boolean[][] arrive;
    static int[] sv;
    static int[] tv;
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), m = Integer.parseInt(strs[1]);
        arrive = new boolean[n + 1][n + 1];
        sv = new int[n + 1];
        tv = new int[n + 1];
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            strs = br.readLine().split(" ");
            int u = Integer.parseInt(strs[0]), v = Integer.parseInt(strs[1]);
            graph[u].add(v);
        }

        for (int i = 1; i <= n; i++) bfs(i);

        //根据arrive数组计算每个点能达到的点数和能达到每个点的点数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arrive[i][j]) {
                    sv[i]++;
                    tv[j]++;
                }
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (tv[i] > sv[i]) res++;
        }
        System.out.println(res);
    }

    //找出i这个点所能到达的所有点并在arrive数组中进行标记
    private static void bfs(int i) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.offer(i);
        arrive[i][i] = true;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (Integer e : graph[cur]) {
                if (!arrive[i][e]) {
                    arrive[i][e] = true;
                    queue.offer(e);
                }
            }
        }
    }
}

发表于 2019-03-13 12:57:54 回复(5)

Python3

Oliver1234

我python用Floyd写会超时。。。所以还是BFS稳妥

最简单粗暴的方法，构建正反向图，分别对俩图BFS统计Sv和Tv的容量并比较。

n, m = map(int, input().split())
ds, dt = {}, {} # ds,dt分别记录正向图，反向图
for i in range(1, n+1):
    ds[i], dt[i] = set([i]), set([i])
for i in range(m):
    x, y = map(int, input().split())
    ds[x].add(y)
    dt[y].add(x)
def bfs(x,d): # 使用bfs
    res = 0
    q = [x]
    visited = [False]*(n+1)
    visited[x] = True
    while q:
        cur = q.pop(0)
        res += 1
        for nxt in d[cur]:
            if not visited[nxt]:
                visited[nxt] = True
                q.append(nxt)
    return res
cnt = 0
for i in range(1,n+1):
    if bfs(i,ds) < bfs(i,dt): cnt += 1
print(cnt)

发表于 2022-02-07 19:14:10 回复(0)

智慧树不长树叶

#include<iostream>
#include<vector>
using namespace std;

int test(vector<vector<int> >side,int n,int m)
{
    int ans = 0;
    if (n == 1 ) return ans;

    //1.建立 临近表
    vector<vector<int> >table_in(n + 1, vector<int>()); //入度表
    vector<vector<int> >table_out(n + 1, vector<int>());//出度表
    for (int i = 0; i < m; i++)
    {
        table_out[side[i][0]].push_back(side[i][1]);
        table_in[side[i][1]].push_back(side[i][0]);
    }

    //2.统计个数
    for (int i = 1; i < n + 1; i++)
    {
        if (table_in[i].size() > table_out[i].size())
            ans++;
        //cout << table_in[i].size() << "-" << table_out[i].size() << endl;
    }

    return ans;
}

int main() {
    //input
    int n, m, ans= 0 ;
    cin >> n >> m;
    vector<vector<int> > side(m+1, vector<int>(2));
    for (int i = 0; i < m; i++)
    {
        cin >> side[i][0] >> side[i][1];
    }
    //系统函数
    ans = test(side, n, m);

    //output，输出重要节点个数（先确定哪些是重要节点），入度大于出度就是重要节点
    cout << ans << endl;
    return 0;
}

过程简洁明了，自己IDE可以跑，测试就出现问题，也不哪里出现问题

发表于 2020-08-09 21:32:23 回复(0)

Java

牛客35031561号

暴力

构建正向图，构建反向图。例如：给定边a->b, 正向图是通过a->b构造的图，反向图是根据b->a构建的图。
依次遍历每个顶点，正向图有多少可以到达的顶点，记为 S,反向图有多少可以到达的顶点，记为 T, S < T, 答案计数一次。从一个顶点遍历其能到达的顶点，可以使用广度优先遍历。

import java.util.*;
public class Main {
    static int bfs(List<Set<Integer>> g, int n, int x) {
        LinkedList<Integer> q = new LinkedList<>();
        boolean used[] = new boolean[n+1];
        q.offer(x);
        int res = 1;
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int item : g.get(cur)) {
                if(used[item] == false) {
                    res ++;
                    q.offer(item);
                    used[item] = true;
                }
            }
        }
        return res;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        List<Set<Integer>> g = new ArrayList<>(); // a -> b
        List<Set<Integer>> g2 = new ArrayList<>(); // b -> a
        for(int i=0; i <= n; i++) {
            g.add(new HashSet<>()); 
            g2.add(new HashSet<>());
        }
        for(int i=0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            if(a != b) {
                g.get(a).add(b);  
                g2.get(b).add(a);  
            }
        }
        int res = 0;
        for(int i=1; i <= n; i++) {
            int s = bfs(g, n, i);
            int t = bfs(g2, n, i);
            if(s < t) res++;
        }
        System.out.println(res);
    }
}

编辑于 2020-06-30 23:50:54 回复(0)

pfeiwang

无语了，把BFS单独作为函数就疯狂提示什么数组，又是栈

发表于 2020-03-09 10:21:03 回复(0)

C/C++

海问香12138

用二维数组Floyd既不会超空间也不会超时

#include <stdio.h>

#define MAXN 1010

int n,m;
int map[MAXN][MAXN];
int T[MAXN];
int S[MAXN];

int main()
{
	int i,j,k,x,y,t,s,sum;
	scanf("%d%d",&n,&m);
	for(i=0;i<m && scanf("%d%d",&x,&y)!=EOF;i++)
		map[x][y] = 1;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
					if(map[i][k]&map[k][j])
						map[i][j] = 1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(map[i][j])
			{
				T[j]++;
				S[i]++;
			}
	for(sum=0,i=1;i<=n;i++)
			sum += T[i]>S[i];
	printf("%d\n",sum);
	return 0;
}

发表于 2019-08-22 11:39:00 回复(0)

insane_reckless

import sys
from collections import deque

if __name__ == "__main__":

    line = raw_input()
    lines = line.split()
    n = int(lines[0])
    m = int(lines[1])
    
    edges = []
    for i in range(m):
        line = raw_input()
        lines = line.split()
        tmp = [int(lines[0]),int(lines[1])]
        if tmp not in edges and tmp[0]!=tmp[1]:
            edges.append(tmp)
    
    adjList = {}
    for idx in range(1,n+1):
        adjList[idx] = []
    
    for i in range(len(edges)):
        b = edges[i]
        adjList[b[0]].append(b[1])
    
    reach = {}
    for idx in range(1,n+1):
        reach[idx] = [idx]
        
    for idx in range(1,n+1):
        stack = deque([])
        visited = [0 for i in range(n+1)]
        stack.append(idx)
        visited[idx] = 1
        while True:
            tmp = stack.popleft()
            for node in adjList[tmp]:
                if visited[node] == 0:
                    visited[node] = 1
                    stack.append(node)
                    reach[idx].append(node)
            if len(stack) == 0:
                break
    
    x = [0 for i in range(n+1)]
    y = [0 for i in range(n+1)]
    
    for idx in range(1,n+1):
        x[idx] = len(reach[idx])
        
    for idx in range(1,n+1):
        times = 0
        for jdx in range(1,n+1):
            if idx in reach[jdx]:
                times += 1
        y[idx] = times
    
    count = 0
    for idx in range(1,n+1):
        if y[idx]>x[idx]:
            count += 1
            
    print count

发表于 2019-05-09 19:56:07 回复(0)

Python

bomnana

70% 通过，不知道卡在哪里啦，很奇怪，哪位大神能解答一下？

#coding:__utf-8__

import queue
def zhongyao_dian(n,m,lists):
Number_count = 0
S = [0 for _ in range(n)]
T = [0 for _ in range(n)]
matrix = [[0 for _ in range(n)]for _ in range(n)]
graph = []
for i in range(n):
graph.append([])
stack = queue.Queue(maxsize=n)

for i in lists:
if i[1] not in graph[i[0]-1]:
graph[i[0]-1].append(i[1]-1)
for i in range(n):
stack.put(i)
while not stack.empty():
cur = stack.get()
for j in graph[cur]:
if matrix[i][j] == 0:
matrix[i][j] = 1
stack.put(j)
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] == 1:
S[i] += 1
T[j] += 1
for i in range(n):
if T[i] - S[i] >0:
Number_count += 1
return Number_count
if __name__ == "__main__":
n, m = [int(i) for i in input().split()]
lists = []
for i in range(m):
lists.append([int(i) for i in input().split()])
quchong_list = []
for i in lists:
if i not in quchong_list:
quchong_list.append(i)
print(zhongyao_dian(n, len(quchong_list), quchong_list))

发表于 2019-04-21 19:17:52 回复(0)