lab6 1000

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<bitset>
 6 #include<vector>
 7 #define rep(i,l,r)for(int i=l;i<r;i++)
 8 #define clr(a,x)memset(a,x,sizeof(a))
 9 using namespace std;
10 bitset<10005>bit[10005];
11 vector<int>e[10005];
12 int t,n,m;
13 bool vis[10005];
14 void dfs(int now)
15 {
16     if(vis[now]) return;
17     vis[now]=1;
18     rep(i,0,e[now].size()){
19         dfs(e[now][i]);
20         bit[now]|=bit[e[now][i]];
21     }    
22 }
23 int main()
24 {    
25     cin>>t;
26     while(t--){
27         clr(vis,0);
28         rep(i,0,n) {
29             bit[i].reset();
30             bit[i][i]=1;
31             e[i].clear();
32         }
33         cin>>n>>m;
34         rep(i,0,m){
35             int from,to;
36             scanf("%d%d",&from,&to);
37             if(from!=to) e[from].push_back(to);
38         }
39         rep(i,0,n)if(!vis[i]) dfs(i);
40         rep(i,0,n) {
41             printf("%d",bit[i].count());
42             if(i!=n-1) printf(" ");
43         }
44         printf("
");
45     }
46     return 0;
47 }

View Code

bitset也是厉害

Description

现在有N个节点，M条边的有向无环图。

我们定义如果存在一条路径从点A到点B，则把B称为A的可达点。

现在我们要求的是这N个点的可达点的个数。

节点编号从0到N-1。

另外，节点自身是自身的可达点。

Input

第一行一个整数T，表示T组数据 (1≤T≤10)

每组数据的第一行有两个正数N和M，表示点数和边数(1≤N≤10000, 1≤M≤50000)

接下来一共有M行，每行两个整数a, b，表示存在一条从a到b的有向边。

由于数据可能存在连到自身的边，遇到这种情况直接CONTINUE掉这条边不用理会。

Output

对于每组测试数据输出一行：

输出N个数，用空格隔开，第i个数表示第i个点的可达点的个数。

Sample Input

Copy sample input to clipboard

Sample Output

1 3 2 1 1 1 2 2 1 1
3 2 1

Hint

考虑一下位运算

Problem Source: Lab06


	Submit