P2017 Dizzy Cows G

### [传送门](https://www.luogu.com.cn/problem/P2017) [USACO09DEC]Dizzy Cows G ###### ~~bike曾说过：‘我们要熟练运用STL’~~ 看到这个有向边无向边，和无环，很容易想到拓扑排序。 **这题可以考虑用dfs和bfs去写** 拓扑排序，记录编号，然后无向边的顺序按排序后序号的大小确定方向 ------------ ## 详细看代码注释 //此处存边是用vector，可邻接表。。。 bfs策略： 如果是有向边，去记录他的入度... 将所有入度为零的点记入容器 在后面每个边的指向的入度--，当点的入度又为0时，再次入队。 这样也就可以使联通的遍历了。 ```cpp #include<bits/stdc++.h> //bfs 版 using namespace std; int n,p1,p2; vector<int >a[100010]; int in[100010];//记录该点的入度 int p,w,cnt; queue<int> q;//其实这里只是需要一个容器，stack也可（大概 int t[100001];//记录位置 int main() { ios::sync_with_stdio(false); cin>>n>>p1>>p2; for(int i=0;i<p1;i++) {//输入有向边 cin>>p>>w; in[w]++;//将指向的点入度++ a[p].push_back(w);//加入 } for(int i=1;i<=n;i++) { if(in[i]==0)//若入度为零 q.push(i);//将其放入容器 } while(q.size()>0) { int x=q.front(); q.pop(); t[x]=cnt++;//放位置 for(int i=0;i<a[x].size();i++) { in[a[x][i]]--; //将此点的边指向的点的入度-- if(in[a[x][i]]==0)//若入度为零 q.push(a[x][i]);//将其入队 } } for(int i=0;i<p2;i++) { cin>>p>>w; if(t[p]<t[w])//观察位置 cout<<p<<" "<<w<<endl; else cout<<w<<" "<<p<<endl; } return 0; } ``` ------------ dfs主要进行编号，但是以单纯以一个点无法全遍历。 注意：这样所求的序是反的。 ```cpp #include<bits/stdc++.h> //dfs 版 using namespace std; int n,p1,p,q,w; vector<int >a[100011];//我们可以去用vector存边 bool v[100011];//记录是否搜过 int t[100011],cnt; //如果 某个点想 void dfs(int x) { for(int i=0;i<a[x].size();i++) { if(!v[a[x][i]])//如果没入容器 dfs(a[x][i]);//以他为下个起点 } v[x]=1;//标记，走过 t[x]=cnt;//编号 cnt++; return ; } int main() { ios::sync_with_stdio(false); cin>>n>>p1>>p2; for(int i=0;i<p1;i++) { cin>>q>>w; a[q].push_back(w);//边 } for (int i=1;i<=n;i++) {//多次，一次dfs很有可能走不完 if(!v[i]) //如果没走过 dfs(i); } for(int i=0;i<p2;i++) { cin>>q>>w; //因为 dfs求的是倒序 if (t[q]>t[w])//所以这里和bfs不同 cout<<q <<" "<<w<<endl; else cout<<w <<" "<<q<<endl; } return 0; } ``` [关于拓扑排序](https://oi-wiki.org/graph/topo/) [关于vector](https://oi-wiki.org/lang/csl/sequence-container/) dfs求拓扑序的板子 ```cpp vector<int> G[MAXN]; // vector 实现的邻接表 int c[MAXN]; // 标志数组 vector<int> topo; // 拓扑排序后的节点 bool dfs(int u) { c[u] = -1; for (int v : G[u]) { if (c[v] < 0) return false; else if (!c[v]) if (!dfs(v)) return false; } c[u] = 1; topo.push_back(u); return true; } bool toposort() { topo.clear(); memset(c, 0, sizeof(c)); for (int u = 0; u < n; u++) if (!c[u]) if (!dfs(u)) return false; reverse(topo.begin(), topo.end()); return true; } ```