首页 > 代码库 > hdu--1269--tarjan<有疑惑>
hdu--1269--tarjan<有疑惑>
这2天 每天学个新的算法吧...可以的话....
tarjan的代码 还是很容易写的 也很容易构图 但总觉得有些细节不那么好理解
传送1
传送2
怎么说呢 总觉得他定义的 low数组含义是有问题的
这是 原作者下的定义
定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号
DFN数组的定义 我觉得没问题...但是 Low[u]数组的定义与我代码检验出来的结果并不相同... 当low[x] low[y] low[z]...low[n]是相等的时候 我们说x y z …………n是在一个连通分量之中的 但是显然我们经过模拟 可以得到如下答案 -- 就是根据那张经典图
6 8
1 2
2 4
4 6
5 6
3 4
3 5
4 1
1 3
标号 i No[i] father[i]
1 1 1
2 6 5
3 2 1
4 5 1
5 3 3
6 4 4
所以 我想low数组的定义不太恰当..
然后 另外一篇博客上是这样介绍的
这样，我们用low值记录该点所在强连通子图对应的搜索子树的根节点的Dfn值。注意，该子树中的元素在栈中一定是相邻的，且根节点在栈中一定位于所有子树元素的最下方
注意下 这边指的最下方 是指在栈这个数据结构之中..因为根结点首先被push进去 然后stack元素入栈是压上面的 所以根结点就在最下面了
如果遍历完整个搜索树后某个点的dfn值等于low值，则它是该搜索子树的根。这时，它以上（包括它自己）一直到栈顶的所有元素组成一个强连通分量‘
这句话 是毫无疑问正确 这也是很重要的一点
强连通分量是由若干个环组成的。所以，当有环形成时（也就是搜索的下一个点已在栈中），我们将这一条路径的low值统一，即这条路径上的点属于同一个强连通分量。
这边 他的说法 又和我的结果有点矛盾...虽然在同一个连通块之中 但是low[]值并没有统一
***********************
还有 这题我做的时候 当我修改了下 father[u] = min( father[u] , No[v] ); ----------->father[u] = min( No[u] , No[v] );
任然是AC的 而且我测了几组的话 输出的dfn low数组也是相同的.....
我就更奇怪了 -.-
要是 我有些想法了 再随时来更新 写下来... 顺便 明天去和porker大神请教下..
1 //横插边：连接到已经出栈的节点的边； 2 //后向边：连接到已在栈中节点的边； 3 //树枝边: 在搜索树中的边。 4 #include <iostream> 5 #include <cstring> 6 #include <stack> 7 #include <algorithm> 8 using namespace std; 9 10 int cnt , n , sum , index; 11 const int size = 10010; 12 int No[size]; 13 int father[size]; 14 bool vis[size]; 15 struct graph 16 { 17 int to; 18 int next; 19 }edge[size*10]; 20 int head[size]; 21 stack<int>s; 22 23 void init( ) 24 { 25 memset( head , -1 , sizeof(head) ); 26 memset( vis , false , sizeof(vis) ); 27 memset( No , 0 , sizeof(No) ); 28 } 29 30 void add( int st , int end ) 31 { 32 while( !s.empty() ) 33 s.pop(); 34 edge[cnt].to = end; 35 edge[cnt].next = head[st]; 36 head[st] = cnt++; 37 } 38 39 void tarjan( int u ) 40 { 41 int temp , v; 42 No[u] = father[u] = index++; 43 vis[u] = true; 44 s.push(u); 45 for( int i = head[u] ; ~i ; i = edge[i].next ) 46 { 47 v = edge[i].to; 48 if( !No[v] ) 49 { 50 tarjan(v); 51 father[u] = min( father[u] , father[v] ); 52 } 53 else if( vis[v] ) 54 { 55 father[u] = min( father[u] , No[v] ); 56 } 57 } 58 if( No[u] == father[u] ) 59 { 60 sum ++; 61 while(1) 62 { 63 temp = s.top(); 64 s.pop(); 65 vis[temp] = false; 66 if( No[temp]==father[temp] ) 67 break; 68 } 69 } 70 } 71 72 int main() 73 { 74 cin.sync_with_stdio(false); 75 int m , x , y; 76 while( cin >> n >> m &&(n||m) ) 77 { 78 init(); 79 sum = cnt = 0; 80 index = 1; 81 while( m-- ) 82 { 83 cin >> x >> y; 84 add(x,y); 85 } 86 for( int i = 1 ; i<=n ; i++ ) 87 { 88 if( !No[i] ) 89 { 90 tarjan(i); 91 } 92 } 93 //for( int i = 1 ; i<= n ;i++ ) 94 //{ 95 // cout << i << " " << No[i] << " " << father[i] << endl; 96 //} 97 if( sum==1 ) 98 cout << "Yes" << endl; 99 else100 cout << "No" << endl;101 }102 return 0;103 }104 /*105 6 8106 1 2107 2 4108 4 6109 5 6110 3 4111 3 5112 4 1113 1 3114 标号 i No[i] father[i]115 1 1 1116 2 6 5117 3 2 1118 4 5 1119 5 3 3120 6 4 4121 */
刚刚翻了下白书上是这样定义的：
low[u]为u及其后代能追溯到的最早<最先被发现>祖先点v的dnf[v]值
today:
回来 本身就是充满悲情色彩的一个词
因为 无论最终他有没有回来
但是 他曾经离开过你
hdu--1269--tarjan<有疑惑>