思想
拓扑，一看就是从图的开始开始开拓，并按被开拓到的顺序排序
拓扑排序的思想如下：
将入度为 \(0\) 的点删除，并记录它被删除的顺序，直到没有点则结束程序
代码也十分简单：
#include<bits/stdc++.h>
using namespace std;
bool b[100001];
int fat[100001];
vector<int>v[100001];
int main(){
int n,m=0;
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
fat[y]++;//记录入度
}
queue<int>q;
for(int i=1;i<=n;i++){
if(fat[i]==0){//将入度为0的点入队
q.push(i);
b[i]=1;
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<v[u].size();i++){
int nn=v[u][i];
fat[nn]--;//入度减少
if(fat[nn]==0){
q.push(nn);//将入度为0的点入队
b[nn]=1;
}
}
}
for(int i=1;i<=n;i++){
if(!b[i])cout<<i<<" "; //也可以判断环上的点
}
return 0;
}
例题
点击查看代码
#include<bits/stdc++.h>
using namespace std;
bool b[100001];
int fat[100001];
vector<int>v[100001];
int main(){
int n,m=0;
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
fat[x]++;
fat[y]++;
}
queue<int>q;
for(int i=1;i<=n;i++){
if(fat[i]==1){
q.push(i);
b[i]=1;
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<v[u].size();i++){
int nn=v[u][i];
fat[nn]--;
if(fat[nn]==1){
q.push(nn);
b[nn]=1;
}
}
}
for(int i=1;i<=n;i++){
if(!b[i])cout<<i<<" ";
}
return 0;
}