拓扑排序入门详解&&Educational Codeforces Round 72 (Rated for Div. 2)-----D

https://codeforces.com/contest/1217

D：给定一个有向图，给图染色，使图中的环不只由一种颜色构成，输出每一条边的颜色

不成环的边全部用1染色

ps:最后输出需要注意，一个环上的序号必然是非全递增的，若有环且有一条边u->v,u的序号<v则输出1否则输出2(反过来也可以)

可以用dfs染色或者用拓扑排序做

顺便复习一下拓扑排序：

拓扑排序是将有向无环图的所有顶点排成一个线性序列，使得图中任意两个顶点u,v若存在u->v，那么序列中u一定在v前面。

了解一个概念: DAG-->有向无环图，一个有向图的任意顶点都无法通过一些有向边回到自身，称之为DAG

算法过程:

(1)定义一个队列，把所有入度为0的结点加入队列(图有n个点)

(2)取队首节点，输出，删除所有从他出发的边，并令这些边的入度-1，若某个顶点的入度减为0，则将其加入队列

(3)反复进行(2)操作，直到队列为空；

注意：若队列为空时入过队的节点数目恰好为n，说明拓扑排序成功，图为DAG，否则图中有环

这位博主写的挺好的 https://blog.csdn.net/qq_41713256/article/details/80805338

 #include<bits/stdc++.h>

 using namespace std;
 inline int read(){
     ,w=;;
     while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
     )+(X<<)+(ch^),ch=getchar();
     return w?-X:X;
 }
 /*-------------------------------------------------------------------*/
 typedef long long ll;
 ;
 int du[maxn];
 ll cnt;
 int n,m;
 int s;
 vector<int>G[maxn];
 pair<int,int>ans[maxn];
 queue<int>q;
 int main()
 {
     ios_base::sync_with_stdio(); cin.tie(); cout.tie();

     //一个环上的序号必然是非全递增的
     cin>>n>>m;
     ;i<=m;i++){

         int u,v;
         cin>>u>>v;

         G[u].push_back(v);

         ans[i].first=u;ans[i].second=v;

         //入度
         du[v]++;
     }

     ;i<=n;i++) ) q.push(i);

     while(!q.empty()){

         int now=q.front();q.pop();

         int len=G[now].size();

         ;i<len;i++){

             du[G[now][i]]--;//该点入度-1 

             )q.push(G[now][i]);

         }
     }
     ;

     ;i<=n;i++)
     ){

         flag=;//标记是否还存在入度不为0的点
         break;
     }
     //一个环上的序号必然是非全递增的 

     if(flag){//说明有环
         cout<<<<endl;
         //for(int i=1;i<=m;i++)cout<<1<<" ";
         ;i<=m;i++){
             if(ans[i].first>ans[i].second)
             cout<<<<" ";
             <<" ";
         }
     }
     else{ //无环直接输出1

         cout<<<<endl;
         ;i<=m;i++)
         cout<<<<" ";
     } 

     ;
 }

DFS版：

dfs过程中有3个状态1，-1，0，1表示当前搜索路径，-1表示已搜索过且无环路径，0表示还未搜索，可以用前向星存边或者vector存边过

其他需要注意的代码有注释

ps:讲个大家不容易理解的地方，这个DFS的点是不是可以从任意起点搜索？答案：是的，这个对拓扑序列没有影响，可通过代码自由验证。

在有向图DFS过程中（不判环的情况下），我们用栈去存储他的拓扑序列，当一个点没有后驱节点时，这个节点入栈，记住栈的性质（后进先出），然后回溯，这样，越是后面的节点就会被压进栈底

比如说有向边u->v,u是v的前驱，若存在u->v>t，t在拓扑序列中一定在u的后面（拓扑排序的性质），我们从v开始搜索，到t终止（无后驱节点），回溯，入栈，v入栈，回溯。

最后我们搜索u，发现u的后驱节点已标记，所以入栈，退出完成拓扑排序

所以，以DFS回溯+栈的形式就可以很好地完成一次拓扑排序

前向星版本：

 #include<bits/stdc++.h>

 using namespace std;
 inline int read(){
     ,w=;;
     while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
     )+(X<<)+(ch^),ch=getchar();
     return w?-X:X;
 }
 /*-------------------------------------------------------------------*/
 typedef long long ll;
 ;
 struct node{
     int to,next;
 }star[];

 ll cnt;
 int n,m;
 int vis[maxn],head[maxn];
 void add(int u,int v){
     star[cnt].to=v;
     star[cnt].next=head[u];
     head[u]=cnt++;
 }
 bool dfs(int idx){

     vis[idx]=;
     ;i=star[i].next){

         int v=star[i].to;
         )return false;
         //若搜索过程中发现回到本次搜索过的点，说明有环，退出
         &&!dfs(v))return false;

     }
     vis[idx]=-;//目前路径上不存在环，所以标记为-1
     return true;
 }
 pair<int,int >p[maxn];
 int main()
 {
     ios_base::sync_with_stdio(); cin.tie(); cout.tie();

     //一个环上的序号必然是非全递增的
     memset(head,-,sizeof(head));
     cin>>n>>m;
     ;i<=m;i++){

         int u,v;
         cin>>u>>v;
         add(u,v);
         p[i].first=u,p[i].second=v;
     }
     ;
     ;i<=n;++i){
         if(!vis[i]){
             if(!dfs(i)){
                 flag=;
                 break;
             }

         }
     }
     if(flag){
         cout<<<<endl;
         ;i<=m;i++){
             <<" ";
             <<" ";
         }
     }
     else{
         cout<<<<endl;
         ;i<=m;i++){
             cout<<<<" ";
         }
     }
     ;
 }

vector版本:

 #include<bits/stdc++.h>

 using namespace std;
 inline int read(){
     ,w=;;
     while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
     )+(X<<)+(ch^),ch=getchar();
     return w?-X:X;
 }
 /*-------------------------------------------------------------------*/
 typedef long long ll;
 ;
 struct node{
     int to,next;
 }star[];

 vector<int>edge[maxn]; 

 ll cnt;
 int n,m;
 int vis[maxn],head[maxn];

 bool dfs(int idx){

     int len=edge[idx].size();
     vis[idx]=;
     ;i<len;++i){

         );
         ;
     }
     vis[idx]=-;
     ;
 }
 pair<int,int >p[maxn];
 int main()
 {
     ios_base::sync_with_stdio(); cin.tie(); cout.tie();

     //一个环上的序号必然是非全递增的
     memset(head,-,sizeof(head));
     cin>>n>>m;
     ;i<=m;i++){

         int u,v;
         cin>>u>>v;

         p[i].first=u,p[i].second=v;

         edge[u].push_back(v);

     }
     ;

     ;i<=n;++i){

         if(!vis[i]){
             if(!dfs(i)){
                 flag=;
                 break;
             }
         }

     }

     if(flag){
         cout<<<<endl;
         ;i<=m;i++){
             <<" ";
             <<" ";
         }
     }
     else{
         cout<<<<endl;
         ;i<=m;i++){
             cout<<<<" ";
         }
     }
     ;
 }

 对拓扑排序讲得还不错的博客：深入理解拓扑排序（Topological sort) - 简书 https://www.jianshu.com/p/3347f54a3187拓扑排序dfs版+判环_Python_姬小野的博客-CSDN博客 https://blog.csdn.net/wjh2622075127/article/details/82712940

巴特西

拓扑排序入门详解&&Educational Codeforces Round 72 (Rated for Div. 2)-----D

顺便复习一下拓扑排序：

ps:讲个大家不容易理解的地方，这个DFS的点是不是可以从任意起点搜索？答案：是的，这个对拓扑序列没有影响，可通过代码自由验证。

最新文章

热门文章