首页 > 代码库 > hdu--3836--tarjan+缩点
hdu--3836--tarjan+缩点
缩点 很简单的啊... 就是将原来一个连通块变成一个点..
可能你原本是这样的 A->B->C->A 缩点完成后 我们就把{A，B,C}用数字1来表示 如果还有D->E->D 那我们再讲{D,E}用2表示....
最后的sum就是代表连通块总的个数
然后 一般 缩点完成后 我们现在得到了n个连通块 我们要考虑的是 最少需要添加几条边来把它串联起来
这样考虑
假如给你2个点 A B 想要让他们联通 需要在他们之间建立两条边 分别是A->B B->A 你会发现这样 A B的入度 出度分别从0变成了1
如果是这样的情况 
那么 现在A的出度为2 入度为0 B和C的出度为0 入度为1 我们只需要B->A C->A建立边就可以了
这样我们就能达到B C的出度增加 A的入度增加
其实 是因为 在任何一个连通图中每个点的入度和出度都是>=1这样才能达到让别人联向自己 自己通向别人
所以 我们只需要求出在缩点完成后的图中 入度为0 与 出度为0的点的个数大小就可以了 取大的
******************
如果是做题的话 有一点要小心 很容易WA在这里..不能直接判断max(in,out)来输出 而是首先判断缩点后的图 是不是连通图 是的话就直接输出0了 如果直接输出max(in,out)就是1了.......
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <stack> 5 using namespace std; 6 7 int n , cnt , index , sum; 8 const int size = 20010; 9 struct data 10 { 11 int st; 12 int end; 13 }node[size*3]; 14 struct graph 15 { 16 int to; 17 int next; 18 }edge[size*3]; 19 int head[size]; 20 int father[size]; 21 int No[size]; 22 int scc[size]; 23 int in[size]; 24 int out[size]; 25 bool vis[size]; 26 stack<int>s; 27 28 void init( ) 29 { 30 memset( head , -1 , int*sizeof(n+10) ); 31 memset( No , 0 , int*sizeof(n+10) ); 32 memset( father , 0 , int*sizeof(n+10) ); 33 memset( vis , false , int*sizeof(n+10) ); 34 memset( scc , 0 , int*sizeof(n+10) ); 35 memset( in , 0 , int*sizeof(n+10) ); 36 memset( out , 0 , int*sizeof(n+10) ); 37 } 38 39 void add( int st , int end ) 40 { 41 edge[cnt].to = end; 42 edge[cnt].next = head[st]; 43 head[st] = cnt ++; 44 } 45 46 void tarjan( int u ) 47 { 48 int v , temp; 49 No[u] = father[u] = index++; 50 vis[u] = true; 51 s.push(u); 52 for( int i = head[u] ; ~i ; i = edge[i].next ) 53 { 54 v = edge[i].to; 55 if( !No[v] ) 56 { 57 tarjan(v); 58 father[u] = min( father[u] , father[v] ); 59 } 60 else if( vis[v] ) 61 { 62 father[u] = min( father[u] , No[v] ); 63 } 64 } 65 if( father[u] == No[u] ) 66 { 67 sum ++; 68 while(1) 69 { 70 temp = s.top(); 71 s.pop(); 72 vis[temp] = false; 73 scc[temp] = sum; 74 if( father[temp] == No[temp] ) 75 break; 76 } 77 } 78 } 79 80 int main() 81 { 82 cin.sync_with_stdio(false); 83 int m , st , end , inMax , outMax; 84 while( cin >> n >> m ) 85 { 86 inMax = outMax = cnt = sum = 0; 87 index = 1; 88 init(); 89 for( int i = 0 ; i<m ; i++ ) 90 { 91 cin >> st >> end; 92 add( st , end ); 93 node[i].st = st; 94 node[i].end = end; 95 } 96 for( int i = 1 ; i<=n ; i++ ) 97 { 98 if( !No[i] ) 99 tarjan(i);100 }101 for( int i = 0 ; i<m ; i++ )102 {103 if( scc[ node[i].st ]!=scc[ node[i].end ] )104 {105 out[ scc[node[i].st] ] ++;106 in[ scc[node[i].end] ] ++;107 }108 }109 for( int i = 1 ; i<=sum ; i++ )110 {111 if( !in[i] )112 inMax ++;113 if( !out[i] )114 outMax ++;115 }116 if( sum==1 )117 cout << "0" << endl;118 else119 cout << max( inMax , outMax ) << endl;120 }121 return 0;122 }
因为 这里的数组要开的TM的实在是太多了 所以我用了 (n)*sizeof(int)来初始化 我测了下 节约了15ms....
today:
后来我终于知道
它并不是我的花
我只是恰好途径了它的盛放
hdu--3836--tarjan+缩点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。