uva 610（割边）-白红宇

uva 610（割边）

阅读量：6112 次

发布时间：2019-06-21

本文共 1956 字，大约阅读时间需要 6 分钟。

题意：这道题很有意思。他是给你一个无向图然后让你把尽量多的边转化成单向边，然后是整张图还是强联通的。

思路：看到这道题的第一反应就是求割边，应为割边所连接的都是双连通分支对于双连通分支我们只需要化成单向边就能解决问题。然后对于割边我们才需要化成双向边。之后我就考虑了一下如何输出答案。这很容易就类似于欧拉通路我开了两个标记数组，一个标记点，另一个标记边。输出一条标记一条即可。注意不要经过桥。然后最后再把所有的桥输出就可以了。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-01-29 15:01 5  * Filename     : uva_610.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 1010;34 int n, m, dclock;35 int bri[LEN][LEN], dfn[LEN], low[LEN], vis[LEN][LEN], vex[LEN], Map[LEN][LEN];36 37 void dfs(int u, int fa){38 dfn[u] = low[u] = dclock++;39 for(int i=1; i<=n; i++){40 if(!Map[u][i]) continue;41 if(dfn[i]<0){42 dfs(i, u);43 low[u] = min(low[u], low[i]);44 if(dfn[u] < low[i]) bri[u][i] = bri[i][u] = 1;45 }else if(low[u] > low[i] && i != fa)low[u] = min(low[u], dfn[i]);46 }47 }48 49 void out(int v){50 vex[v] = 1;51 for(int i=1; i<=n; i++){52 if(!Map[v][i] || bri[v][i] || vis[v][i]) continue;53 vis[v][i] = vis[i][v] = 1;54 cout << v << ' ' << i << endl;55 out(i);56 }57 }58 59 int main()60 {61 // freopen("in.txt", "r", stdin);62 63 int a, b;64 for(int kase = 1; scanf("%d%d", &n, &m)!=EOF; kase++){65 if(!n && !m) break;66 memset(Map, 0, sizeof Map);67 printf("%d\n\n", kase);68 for(int i=0; i

View Code

转载于:https://www.cnblogs.com/shu-xiaohao/p/3536224.html

你可能感兴趣的文章

加解密算法、消息摘要、消息认证技术、数字签名与公钥证书