Stable Members
题目链接：http://hihocoder.com/problemset/problem/1343
题目大意：给一个有向无环图,定义一个点为unstable当且仅当删掉一个点（不能为它自己或点0）时，它不能与点0连通；其他点则为stable，求图中有几个stable点。
思路：
如果一个点是Stable点的话，那么它的到达该点的路径肯定是不止一条（并且路径没有交叉）的。如果我们采取染色的方法，那么也就是说遍历它的父亲结点及以上的结点不可以都是一样的（因为如果都是一样的话那么就说明发生路径交叉了）。
对于每个顶点v，采用染色的方法：即对于某个顶点v，采用拓扑排序的方法遍历其后续顶点，并依次染色。后续的顶点进入队列的条件是，其所有的父顶点都已经被染成顶点v的颜色。
1 #include <math.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <iostream> 5 #include <algorithm> 6 #include <string> 7 #include <string.h> 8 #include <vector> 9 #include <map> 10 #include <stack> 11 #include <set> 12 #include <queue> 13 14 15 #define LL long long 16 #define INF 0x3f3f3f3f 17 #define ls nod<<1 18 #define rs (nod<<1)+1 19 20 const int maxn = 2e5 + 10; 21 const int mod = 142857; 22 23 int col[maxn],un[maxn]; 24 std::vector<int> son[maxn],parent[maxn]; 25 26 bool all_same(int now,int color) { 27 int len = parent[now].size(); 28 for (int i=0;i<len;i++) { 29 if (col[parent[now][i]] != color) 30 return false; 31 } 32 return true; 33 } 34 35 36 37 void topsort(int x) { 38 if (col[x] != 0) 39 return; 40 col[x] = x; 41 std::queue<int> q; 42 q.push(x); 43 while (!q.empty()) { 44 int now = q.front(); 45 q.pop(); 46 int len = son[now].size(); 47 for (int i=0;i<len;i++) { 48 if (all_same(son[now][i],col[now])) { 49 col[son[now][i]] = col[now]; 50 q.push(son[now][i]); 51 un[son[now][i]] = 1; 52 } 53 } 54 } 55 } 56 57 58 59 int main() { 60 int n; 61 scanf("%d",&n); 62 for (int i=1;i<=n;i++) { 63 int k,id; 64 scanf("%d",&k); 65 while (k--) { 66 scanf("%d",&id); 67 parent[i].push_back(id); 68 son[id].push_back(i); 69 } 70 } 71 for (int i=1;i<=n;i++) 72 topsort(i); 73 int ans = 0; 74 for (int i=1;i<=n;i++) { 75 ans += un[i]; 76 } 77 printf("%d\n",n-ans); 78 return 0; 79 }
投递58到家等公司7个岗位 >