Coloring Edges 【拓扑判环】

题目链接：https://vjudge.net/contest/330119#problem/A

题目大意：

1.给出一张有向图，给该图涂色，要求同一个环里的边不可以全部都为同一种颜色。问最少需要多少颜色，并输出各边的涂色。

解题思路：

1.多画几张图就发现，颜色种类只会是1或者2。当不存在环的时候，全部涂1。当存在环的时候，环中可以分成两种边（小节点指向大节点涂1，大节点指向小节点涂2），就会发现所有的环颜色一定不会全部相同。

2.思考过1就发现这道题只需要判断是否存在环即可。可以用拓扑判断。原理为：在拓扑的过程中，入度为0的点会入队，但由于环上各点入度不可能为0.因此无法入队。所以在拓扑结束后，还存在没有入队的点，即存在环。

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 #define mem(a, b) memset(a, b, sizeof(a))

 const int MAXN = ;

 const int MAXM = ;

 using namespace std;

 int n, m;

 int head[MAXN], cnt, in[MAXN], out[MAXN], tot;

 queue<int> Q;

 struct Edge

 {

     int from, to, next;

 }edge[MAXM];

 void add(int a, int b)

 {

     cnt ++;

     edge[cnt].from = a;

     edge[cnt].to = b;

     edge[cnt].next = head[a];

     head[a] = cnt;

 }

 int topo()

 {

     for(int i = ; i <= n; i ++)

     {

         if(!in[i])

         {

             Q.push(i);

             tot ++;

         }

     }

     while(!Q.empty())

     {

         int temp = Q.front();

         Q.pop();

         for(int i = head[temp]; i != -; i = edge[i].next)

         {

             int to = edge[i].to;

             in[to] --;

             if(!in[to])

             {

                 Q.push(to);

                 tot ++;

             }

         }

     }

     if(tot != n) //存在 点 没有入队

         return ;

     else

         return ;

 }

 int main()

 {

     scanf("%d%d", &n, &m);

     mem(head, -);

     for(int i = ; i <= m; i ++)

     {

         int a, b;

         scanf("%d%d", &a, &b);

         in[b] ++, out[a] ++;

         add(a, b);

     }

     if(topo()) //判是否有环存在

     {

         printf("2\n");

         int flag = ;

         for(int i = ; i <= cnt; i ++)

         {

             int a = edge[i].from, b = edge[i].to;

             if(flag)

             {

                 if(a < b)

                     printf("");

                 else

                     printf("");

                 flag = ;

             }

             else

             {

                 if(a < b)

                     printf("");

                 else

                     printf("");

             }

         }

         printf("\n");

     }

     else

     {

         printf("1\n1");

         for(int i = ; i < m; i ++)

             printf("");

         printf("\n");

     }

     return ;

 }

巴特西

Coloring Edges 【拓扑判环】

最新文章

热门文章