HUST——1103Party（拓扑排序+个人见解）

1103: Party

Time Limit: 2 Sec Memory Limit: 64 MB
Submit: 11 Solved: 7

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.

今天找了篇博客认真看了下拓扑排序，想自己重新写下这道题。一次就过了运气不错。（很多东西重新回过头来看会有更深入的理解和发现）仔细思考一下确实如文章所说：

不难看出该算法的实现十分直观，关键在于需要维护一个入度为0的顶点的集合：

每次从该集合中取出(没有特殊的取出规则，随机取出也行，使用队列/栈也行，下同)一个顶点，将该顶点放入保存结果的List中。

紧接着循环遍历由该顶点引出的所有边，从图中移除这条边，同时获取该边的另外一个顶点，如果该顶点的入度在减去本条边之后为0，那么也将这个顶点放到入度为0的集合中。然后继续从集合中取出一个顶点…………

当集合为空之后，检查图中是否还存在任何边，如果存在的话，说明图中至少存在一条环路。不存在的话则返回结果List，此List中的顺序就是对图进行拓扑排序的结果。

首先要知道一点入度和出度的概念，比如我在学数学之前要学语文，此时语文和数学之间有一个箭头，那按正常思维肯定是语文比数学优先吧，因为你肯定要先学语文才能学数学啊，那么就在语文和数学之间连一条有向边，就像这样语文——>数学，可以当成你玩游戏时的进度，过了语文这个任务才能过数学。嗯这样应该非常好理解了吧。

因此需要用到三个东西使得程序易于实现和理解

1、容器数组：是记录每一个顶点a所指向的顶点bi的集合；

比如1——>2那么我们就在vector[1]中压入2这个点。

2、入度数组：记录每一个顶点的入度。显然例子中rudu[数学]=1;

3、维护每次找到的入度为0的队列：拓扑排序可以看成一种模拟——首先找到入度为0的即没人可以制约它的点，然后将这个点和它指出去的边删去，此时它连到的点入度肯定会因此减1（平凡图情况下）。那么很可能此时又会产生一个/多个入度为0的点。然后又可以重复前面步骤了。直到找不到入度为0的点或者所有边已经访问过。

那拓扑归拓扑，排序是什么鬼？就是每次出现的入度变为0的点按照出现的先后顺序构成的一个序列。用容器或者数组加一个尾指针来保存就可以。当然此题不需要输出排序结果。

代码（注释内容可以输出排序结果）：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long LL;
int const N=100010;
int rudu[N];
vector<int>V[N];
inline void init(int n)
{
	for (int i=0; i<=n; i++)
	{
		V[i].clear();
	}
	MM(rudu);
}
int main(void)
{
	int tcase,i,j,a,n,m,sum;
	scanf("%d",&tcase);
	while (tcase--)
	{
		queue<int>Q;
		scanf("%d",&n);
		sum=0;init(n);
		for (i=1; i<=n; i++)
		{
			scanf("%d",&m);
			if(m==0)
			{
				Q.push(i);
				continue;
			}	
			for (j=1; j<=m; j++)
			{
				scanf("%d",&a);
				V[a].push_back(i);
			}
			rudu[i]+=m;
			sum+=m;
		}
		//vector<int>ans;
		while (!Q.empty())
		{
			int now=Q.front();
			Q.pop();
			int sz=V[now].size();
			for (i=0; i<sz; i++)
			{
				int v=V[now][i];
				rudu[v]--;
				sum--;
				if(rudu[v]==0)
				{
					Q.push(v);
					//ans.push_back(v);
				}
			}
		}
		if(sum)
			puts("No");
		else
		{
			puts("Yes");
			/*for (vector<int>::iterator it=ans.begin(); it!=ans.end(); it++)
			{
				printf("%d ",*it);
			}
			putchar('
');*/
		}	
	}
	return 0;
}