HUST 1103 校赛邻接表-拓扑排序

Description

N students were invited to attend a party, every student has some friends, only if someone’s all friends attend this party, this one can attend the party(ofcourse if he/she has no friends, he/she also can attend it.), now i give the friendship between these students, you need to tell me whether all of them can attend the party.

Note that the friendship is not mature, for instance, if a is b’s friend, but b is not necessary a’s friend.

Input

Input starts with an integer T(1 <= T <= 10), denoting the number of test case.

For each test case, first line contains an integer N(1 <= N <= 100000), denoting the number of students.

Next n lines, each lines first contains an integer K, denoting the number of friends belong to student i(indexed from 1). Then following K integers, denoting the K friends.

You can assume that the number of friendship is no more than 100000, and the relation like student A is himself’s friend will not be existed.

Output

For each test case, if all of the students can attend the party, print Yes, otherwise print No.

Sample Input

Sample Output

No
Yes

HINT

For the first case:

Student 1 can attend party only if student 2 attend it.

Student 2 can attend party only if student 3 attend it.

Student 3 can attend party only if student 1 attend it.

So no one can attend the party.

题意：给定n个人，第i个人依赖k个人，只有k个人都参加了，那么i才会参加。问是否所有人都能参加。

思路：数据量有些大，可能无法用并查集判是否有回路解。学长给出方法是用拓扑排序，最后将节点数量和n比较判断即可。

拓扑排序大致是查找出度为零的所有节点，压入队列，一个个弹出，同时将该点和临边删除。

用到了Vector邻接表，发现储存图真是好用。

但是我的代码还有点问题，vector并不需要开二维的，一维就够了。

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <utility>
 8 #define  MAXX 100010
 9 using namespace std;
10 const int  INF = 0x3f3f3f3f;
11 pair<vector<int>, int> x;
12 vector< vector<int> >bel(100010);
13 queue< vector<int> >qu;
14 int a[MAXX];
15 int cnt;
16 
17 int findpush(int n)
18 {
19     int flag = 1;
20     for(int i = 1; i <= n; i++)
21     {
22         if(a[i] == 0)
23         {
24             flag = 0;
25             if(bel[i].size())
26                 qu.push(bel[i]);
27             else 
28                 cnt--;
29             a[i] = INF;
30         }
31     }
32     return flag;
33 }
34 
35 int main()
36 {
37     int T, n, t, ed;
38     scanf("%d", &T);
39     while(T--)
40     {
41         scanf("%d",&n);
42         cnt = n;
43 
44         for(int i = 1; i <= n; i++)
45             a[i] = 0, bel[i].clear();
46         for(int i = 1; i <= n; i++)
47         {
48             scanf("%d", &t);
49            /* if(!t)
50                 cnt--;*/
51             while(t--)
52             {
53                 scanf("%d", &ed);
54                 bel[ed].push_back(i);
55                 a[i]++;
56             }
57         }
58         while(qu.empty())
59         {
60             int flag = findpush(n);
61             if(flag == 1)
62             {
63                 if(cnt)
64                     printf("No
");
65                 else printf("Yes
");
66                 break;
67             }
68             int temp = qu.size();
69             while(temp--)
70             {
71 
72                 for(int i = 0; i < (qu.front()).size(); i++)
73                 {
74                     a[(qu.front())[i] ]--;
75                 }
76                 qu.pop();
77                 cnt--; 
78             }        
79         }
80     }
81 }