tarjan算法

lca就好了，不难理解

hdu1269：

模板题

-------------------------------------------------------------------------------------------

poj2186：

只会有一个scc属于。

-------------------------------------------------------------------------------------------

poj1236：

求加最少几条边能使整个图强连通。注意scc的入度和出度挺能用的；

-------------------------------------------------------------------------------------------

hdu2767：

终于写的有点熟了，20minac

------------------------------------------------------------------------------------------

hdu3072：

缩点求最短路径即可；

------------------------------------------------------------------------------------------

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<stack>
 5 #include<algorithm>
 6 using namespace std;
 7 #define rep(i,n) for(int i=1;i<=n;i++)
 8 #define clr(x,c) memset(x,c,sizeof(x))
 9 struct edge{
10     int to,dis,next;
11 };
12 edge e[100005];
13 int dfn[50005],low[50005],h[50005],v[50005],cot[50005];
14 int dfn_clock,scc_cnt,n,m;
15 stack<int>s;
16 int read(){
17     int x=0;
18     char c=getchar();
19     while(!isdigit(c)) c=getchar();
20     while(isdigit(c)){
21         x=x*10+c-'0';
22         c=getchar();
23     }
24     return x;
25 }
26 int tarjan(int x){
27     dfn[x]=low[x]=++dfn_clock;
28     s.push(x);
29     for(int i=h[x];i;i=e[i].next){
30         int y=e[i].to;
31         if(!dfn[y]){
32             tarjan(y);
33             low[x]=min(low[x],low[y]);
34         }
35         else if(!v[y]){
36             low[x]=min(low[x],dfn[y]);
37         }
38     }
39     if(low[x]==dfn[x]){
40         scc_cnt++;
41         while(1){
42             int o=s.top();
43             s.pop();
44             v[o]=scc_cnt;
45             if(o==x)
46               break;
47         }
48     }
49 }
50 int main(){
51     while(scanf("%d%d",&n,&m)!=EOF){
52         int cur=dfn_clock=scc_cnt=0;
53         clr(dfn,0);clr(low,0);clr(h,0);clr(v,0);clr(cot,0x7f);
54         while(!s.empty()){
55             s.pop();
56         }
57         rep(i,m){
58             int u=read(),v=read(),o=read();
59             e[++cur].to=v+1;
60             e[cur].dis=o;
61             e[cur].next=h[u+1];
62             h[u+1]=cur;
63         }
64         rep(i,n) 
65           if(!dfn[i])
66             tarjan(i);
67         int ans=0;
68         rep(i,n)
69             for(int j=h[i];j;j=e[j].next)
70                 if(v[i]!=v[e[j].to]){
71                     cot[v[e[j].to]]=min(cot[v[e[j].to]],e[j].dis);
72                 }
73         rep(i,scc_cnt){
74             if(cot[i]<0x3f3f3f3f)
75               ans+=cot[i];
76         }
77         printf("%d
",ans);
78     }
79     return 0;
80 }

------------------------------------------------------------------------------------------