HDU 4612 Warm up(Tarjan)

果断对Tarjan不熟啊，Tarjan后缩点，求树上的最长路，注意重边的处理，借鉴宝哥的做法，开标记数组，标记自己的反向边。
  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <queue>
  6 #include <cstdlib>
  7 using namespace std;
  8 #define N 200001
  9 #define M 2000001
 10 #define INF 0x3f3f3f3f
 11 struct node
 12 {
 13     int u,v,next;
 14 }edge[M];
 15 struct na
 16 {
 17     int u,v,w,next;
 18 }tree[M];
 19 int first[N],DFN[N],Belong[N],stack[N],Low[N],cnum[N];
 20 int in[N],d[N],fr[N];
 21 int qu[M],qv[M];
 22 int n,m;
 23 bool vis[M];
 24 int tot,scnt,top;
 25 void CL()
 26 {
 27     tot = scnt = top = 0;
 28     memset(first,-1,sizeof(first));
 29     memset(fr,-1,sizeof(fr));
 30     memset(in,0,sizeof(in));
 31     memset(DFN,0,sizeof(DFN));
 32     memset(vis,0,sizeof(vis));
 33 }
 34 void add(int u,int v)
 35 {
 36     edge[tot].u = u;
 37     edge[tot].v = v;
 38     edge[tot].next = first[u];
 39     first[u] = tot ++;
 40 }
 41 void addt(int u,int v)
 42 {
 43     tree[tot].u = u;
 44     tree[tot].v = v;
 45     tree[tot].w = 1;
 46     tree[tot].next = fr[u];
 47     fr[u] = tot ++;
 48 }
 49 void Tarjan(int u,int num)
 50 {
 51     int v,i;
 52     DFN[u] = Low[u] = ++ tot;
 53     stack[top++] = u;
 54     in[u] = 1;
 55     for(i = first[u];i != -1;i = edge[i].next)
 56     {
 57         v = edge[i].v;
 58         if(vis[i]) continue;
 59         vis[i] = vis[i^1] = 1;
 60         if(!DFN[v])
 61         {
 62             //printf("cc%d %d",v,i);
 63             Tarjan(v,i);
 64             Low[u] = min(Low[u],Low[v]);
 65         }
 66         else if(in[v])
 67         {
 68             Low[u] = min(Low[u],DFN[v]);
 69         }
 70     }
 71     if(DFN[u] == Low[u])
 72     {
 73         scnt ++;
 74         do
 75         {
 76             v = stack[--top];
 77             Belong[v] = scnt;
 78             in[v] = 0;
 79             cnum[scnt] ++;
 80         }while(u != v);
 81     }
 82 }
 83 int spfa(int x)
 84 {
 85     int i,key,v,u,minz = 0;
 86     for(i = 1;i <= scnt;i ++)
 87     {
 88         in[i] = 0;
 89         d[i] = INF;
 90     }
 91     queue<int> que;
 92     in[x] = 1;
 93     d[x] = 0;
 94     que.push(x);
 95     while(!que.empty())
 96     {
 97         u = que.front();
 98         in[u] = 0;
 99         que.pop();
100         for(i = fr[u];i != -1;i = tree[i].next)
101         {
102             v = tree[i].v;
103             if(d[v] > d[u] + tree[i].w)
104             {
105                 d[v] = d[u] + tree[i].w;
106                 if(!in[v])
107                 {
108                     in[v] = 1;
109                     que.push(v);
110                 }
111             }
112         }
113     }
114     for(i = 1;i <= scnt;i ++)
115     {
116         if(minz < d[i])
117         {
118             minz = d[i];
119             key = i;
120         }
121     }
122     return key;
123 }
124 int main()
125 {
126    
127     int i,u,v,str,x;
128     while(scanf("%d%d",&n,&m)!=EOF)
129     {
130         if(n == 0&&m == 0) break;
131         CL();
132         for(i = 1;i <= m;i ++)
133         {
134             scanf("%d%d",&u,&v);
135             if(i == 1)
136             str = u;
137             qu[i] = u;
138             qv[i] = v;
139             add(u,v);
140             add(v,u);
141         }
142         tot = 0;
143         Tarjan(u,0);
144         tot = 0;
145         for(i = 1;i <= m;i ++)
146         {
147             if(Belong[qu[i]] != Belong[qv[i]])
148             {
149                 addt(Belong[qu[i]],Belong[qv[i]]);
150                 addt(Belong[qv[i]],Belong[qu[i]]);
151             }
152         }
153         if(scnt == 1)
154         printf("0
");
155         else
156         {
157             x = spfa(spfa(1));
158             printf("%d
",scnt-d[x]-1);
159         }
160     }
161     return 0;
162 }