一.拓扑排序
1.定义：
设G=（V，E）是一个具有n个顶点的有向图，V中的顶点序列称为一个拓扑序列，当且仅当满足下列条件：若从顶点
到
有一条路径，则在顶点序列中顶点
必在
之前。
2.基本思想：
（1）从AOV网中选择一个没有前驱的顶点并且输出；
（2）从AOV网中删除该顶点，并且删去所有以该顶点为头的的弧；
（3）重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。
二.实战演练
1.问题描述：
小明的实验室有 N 台电脑，编号1⋯N。原本这 N 台电脑之间有 N−1 条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了 BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
2.输入描述：
输入范围：
第一行包含一个整数 N 。
以下 N 行每行两个整数 a,b，表示 a 和 b 之间有一条数据链接相连。
其中， 1≤N≤10^5，1≤a,b≤N。
输入保证合法。
3.输出描述：
按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。
dfs+拓扑排序实现：
//发现环
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const long long N=1e5+10;
vector <int> v[N];
vector <int> result;
int d[N]={0};
bool vis[N]={false};
void dfs(int x){
vis[x]=true;
for(int i=0;i<v[x].size();i++){
d[v[x][i]]--;
if(d[v[x][i]]==1){
dfs(v[x][i]);
}
}
}
void solve(int n){
for(int i=1;i<=n;i++){
if(d[i]==1){
dfs(i);
}
}
for(int i=1;i<=n;i++){
if(vis[i]==false){
result.push_back(i);
}
}
sort(result.begin(),result.end());
for(int i=0;i<result.size();i++){
cout<<result[i]<<' ';
}
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,a,b;
cin>>n;
for(int i=0;i<n;i++){
cin>>a>>b;
d[a]++;d[b]++;
v[a].push_back(b);
v[b].push_back(a);
}
solve(n);
return 0;
}
vector中的begin与end
begin返回向量头指针，指向第一个元素。
end返回向量尾指针，指向向量最后一个元素的下一个位置。
bfs+拓扑排序实现：
//发现环
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const long long N=1e5+10;
vector <int> v[N];
vector <int> result;
int d[N]={0};
bool vis[N]={false};
queue <int> q;
void bfs(int n){
int u;
for(int i=1;i<=n;i++){
if(d[i]==1){
q.push(i);//入队
vis[i]=true;//标记为已经搜索过
}
}
while(!q.empty()){
u=q.front();//取出队头
q.pop();
for(int i=0;i<v[u].size();i++){//搜索邻接点
d[v[u][i]]--;
if(d[v[u][i]]==1){
q.push(v[u][i]);
vis[v[u][i]]=true;
}
}
}
for(int i=1;i<=n;i++){
if(vis[i]==false){
result.push_back(i);
}
}
sort(result.begin(),result.end());
for(int i=0;i<result.size();i++){
cout<<result[i]<<' ';
}
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,a,b;
cin>>n;
for(int i=0;i<n;i++){
cin>>a>>b;
d[a]++;d[b]++;
v[a].push_back(b);
v[b].push_back(a);
}
bfs(n);
return 0;
}
