Uva 796 Critical Links (割边+排序)

题目链接：

题目描述：

　　题目中给出一个有可能不连通的无向图，求出这个图的桥，并且把桥按照起点升序输出（还有啊，还有啊，每个桥的起点要比终点靠前啊），这个题目读了好几遍，但是依旧没有找到数据范围写在哪里，经过无数次runtime error最终把范围定在1W左右。（题目晦涩难懂，wa到死了，嗷~~~~~~）

解题思路：

　　就是用Tarjan算法dfs出low和dfn数组，然后记录下来起点和终点排好序的桥，然后把桥排序输出就ok了。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 struct node

 {

     int to, next;

 } edge[maxn*];

 bool cmp (node a, node b)

 {

     if (a.next == b.next)

         return a.to < b.to;

     return a.next < b.next;

 }

 int low[maxn], dfn[maxn], head[maxn];

 int Father[maxn], tot, ntime, cnt;

 node Q[maxn * ];

 void init ()

 {

     ntime = tot = cnt = ;

     memset (low, , sizeof(low));

     memset (dfn, , sizeof(dfn));

     memset (head, -, sizeof(head));

     memset (Father, , sizeof(Father));

 }

 void Add (int from, int to)

 {

     edge[tot].to = to;

     edge[tot].next = head[from];

     head[from] = tot ++;

 }

 void Tarjan (int u, int father)

 {

     low[u] = dfn[u] = ++ntime;

     Father[u] = father;

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

     {

         int v = edge[i].to;

         if (!dfn[v])

         {

             Tarjan (v, u);

             low[u] = min (low[u], low[v]);

         }

        else if (father != v)

             low[u] = min (low[u], dfn[v]);

     }

 }

 int main ()

 {

     int n, m;

     node q;

     while (scanf ("%d", &n) != EOF)

     {

         init ();

         m = n;

         while (n --)

         {

             int u , k;

             scanf ("%d (%d)", &u, &k);

             while (k --)

             {

                 int v;

                 scanf ("%d", &v);

                 Add (u, v);

                 Add (v, u);

             }

         }

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

             if (!dfn[i])

                 Tarjan (i, -);

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

         {

             int v = Father[i];

             if (v != - && dfn[v] < low[i])

             {

                 q.next = v;

                 q.to = i;

                 if (q.next > q.to)

                     swap(q.next, q.to);

                 Q[cnt++] = q;

             }

         }

         printf ("%d critical links\n", cnt);

         sort (Q, Q+cnt, cmp);

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

             printf ("%d - %d\n", Q[i].next, Q[i].to);

         printf ("\n");

     }

     return ;

 }

巴特西

Uva 796 Critical Links (割边+排序)

最新文章

热门文章