题目来源：
https://hihocoder.com/problemset/problem/1175
http://acm.hdu.edu.cn/showproblem.php?pid=2647
第一题是一个最基本的拓扑排序，第二题可以理解为第一题的逆向思维。那么从第一题开始说起。
在此之间先了解几个概念
有向无环图
比如a可以到b但是b不能到a，那么我们称a到b是有向的，相反的a和b之间可以互相抵达则是无向的，无向图在并查集的有涉及到。
这里的第一题是保证数据是有向无环图的，第二题不保证，怎么处理后面细说。
vecter
这题是我第一用vector，关于vector怎么使用会在代码中注释出来，这里就不细说。
说完了这些来看第一题病毒的传播，这一题要怎么实现题目都已经说了，这里简单说一下，给出病毒传输的路径，病毒不会逆向传播，从开端开始，把所有的开端压入队列，之后对开端能达到的病毒进行遍历，统计他们的病毒数目，并且每次将入度（即为有几个点能到达这个点）为0的病毒压入队列，直到遍历完所有的病毒位置。
下面通过代码来细说
#include<iostream> #include<queue> #include<vector> #define m 142857 using namespace std; queue<int> q;//创建队列用来遍历点 vector<int> vec[100005];//创建数组用来存该点可以到哪几个点 int num[100005];//用来存该点的病毒数目 int tree[100005];//存该点的入度 int main() { int N,M,K,a,b,cnt=0; cin>>N>>M>>K; for(int i=1;i<=K;i++) { cin>>a; num[a]++; } for(int i=1;i<=M;i++) { cin>>a>>b; vec[a].push_back(b);//a能到b，所以将b压入a数组 tree[b]++;//b的入度加一 } for(int i=1;i<=N;i++)//找到所有的起点即入度为0的点 if(tree[i]==0) q.push(i); while(!q.empty())//开始对每一个数据进行处理 { a=q.front(); q.pop(); cnt+=num[a];//统计总共的病毒数 cnt%=m; for(int i=0;i<vec[a].size();i++)//对a能到达的每一个点进行处理 { b=vec[a][i]; num[b]+=num[a];//统计病毒数 tree[b]--;//入度减一 num[b]%=m; if(tree[b]==0)//入度为零，压入队列 q.push(b); } } cout<<cnt%m; return 0; }
这是第一题，下面来看第二题，先说下题意一个分配工资的问题，题目给出所有人物之间的比较关系，要求输出最少的工资，若不满足所有人的要求，则输出-1。
那么这一题跟第一题很类似，但是又有几个不同的地方，下面我举例子来进行说明，第一个是什么时候输出-1。
看这个例子，3要比2多，4要比3多，2要比4多，很显然不成立，所以输出-1，那么也就说明了一旦成环，就不成立。在程序里如何判断就是根据有没有遍历全部的数，我们可以看出起点只有1，但是当1处理到2的时候，2的入度为2，减一后为1还是不为零，不会进入队列，所以程序到此结束，那么2，3，4都没有遍历，根据环的特性我们可以知道拓扑排序的方法是不会进入环的，那么我们只要记录一共处理了多少个点，和总的点判断就可以了。
还有一个不同的地方
这个例子里，2要比1多，3要比1多，那么假设1需要的工资为0的话，如果按照第一的方式，那么2和3需要的工资就为1，那么需要的总工资为2，这显然是错误的，正确的结果应该是2和3需要的为0，而1需要的工资为1，总工资为1，所以这一题就要反向建图，这是第二个不同点。
下面看完整代码
#include<iostream> #include<vector> #include<queue> #include<stdio.h> #include<cstring> using namespace std; int n,m,num,ans; vector<int> vec[10005]; queue<int> q; int main() { int a,b; int tree[10005]; int cnt[10005];//假设最小的工资为0，在此基础上每当需要增加的时候就加一 while(scanf("%d",&n)!=EOF) { cin>>m; ans=888*n;//先计算出所有人的基本工资，方便后期计算。 //因为是不定组输入，所以这里每一组数据都需要初始化 memset(tree,0,sizeof(tree));//初始化 memset(cnt,0,sizeof(cnt));//初始化 for(int i=0;i<=10004;i++)//初始化 { vec[i].clear(); } num=0; for(int i=1;i<=m;i++) { cin>>a>>b; vec[b].push_back(a);//注意，这里是反向，把a设为b能到达的点 tree[a]++;//a的入度加一 } for(int i=1;i<=n;i++)//统计所有的起点 if(tree[i]==0) { q.push(i); num++; } while(!q.empty())//处理所有的数据 { a=q.front(); q.pop(); for(int i=0;i<vec[a].size();i++) { b=vec[a][i]; cnt[b]=cnt[a]+1;//因为b工资要比a多，所以在a的基础上加一 tree[b]--;//b的入度减一 if(tree[b]==0)//若入度为零，就压入队列 { q.push(b); num++; } } } if(num!=n)//查是不是搜索到了所有的点，若没有搜索到，则说明存在成环的情况 cout<<"-1"<<; else { for(int i=1;i<=n;i++)//遍历所有的点，将所有需要增加的工资加初始工资里 { ans+=cnt[i]; } cout<<ans<<endl; } } return 0; }