POJ 3177 Redundant Paths

先找双连通分量缩点，然后找桥重新构图成树，然后找树的叶子节点
答案是：(树的叶子节点+1)/2
顺便附上双连通分量的模板
  1 //#pragma comment(linker, "/STACK:102400000,102400000")
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<string>
  6 #include<cmath>
  7 #include<set>
  8 #include<list>
  9 #include<map>
 10 #include<iterator>
 11 #include<cstdlib>
 12 #include<vector>
 13 #include<queue>
 14 #include<stack>
 15 #include<algorithm>
 16 #include<functional>
 17 using namespace std;
 18 typedef long long LL;
 19 #define ROUND(x) round(x)
 20 #define FLOOR(x) floor(x)
 21 #define CEIL(x) ceil(x)
 22 const int maxn=5010;
 23 const int maxm=20010;
 24 const int inf=0x3f3f3f3f;
 25 const LL inf64=0x3f3f3f3f3f3f3f3fLL;
 26 const double INF=1e30;
 27 const double eps=1e-6;
 28 
 29 /**
 30 *双连通分量：Tarjan算法($O(V+E)$)
 31 *输入：图(链式前向星),n
 32 *输出：bcc[](双连通分量)
 33 */
 34 struct Edge
 35 {
 36     int v;
 37     int next;
 38 }edge[maxm];
 39 int head[maxn],edgeNum;
 40 void addSubEdge(int u,int v)
 41 {
 42     edge[edgeNum].v=v;
 43     edge[edgeNum].next=head[u];
 44     head[u]=edgeNum++;
 45 }
 46 void addEdge(int u,int v)
 47 {
 48     addSubEdge(u,v);
 49     addSubEdge(v,u);
 50 }
 51 int n,m;
 52 int mark[maxn],low[maxn];    //mark初始化为0
 53 int sstack[maxn],stop;        //top初始化为0
 54 int dfn;                    //初始化为1
 55 int bcc[maxn],bid;            //bid初始化为1
 56 int dfs(int k,int p)
 57 {
 58     int i,j;
 59     low[k]=mark[k]=dfn++;
 60     sstack[stop++]=k;
 61     for(i=head[k]; i!=-1; i=edge[i].next)
 62     {
 63         j=edge[i].v;
 64         if(mark[j]==0)
 65         {
 66             dfs(j,k);
 67             low[k]=min(low[k],low[j]);
 68         }
 69         else if(j!=p) low[k]=min(low[k],mark[j]);
 70     }
 71     if(mark[k]>low[k])return 0;
 72     while(sstack[--stop]!=k)// 导出一个双连通分量
 73     {
 74         bcc[sstack[stop]]=bid;
 75     }
 76     bcc[k]=bid;
 77     ++bid;
 78     return 0;
 79 }
 80 /*Dfs调用*/
 81 void tarjan()
 82 {
 83     memset(mark,0,sizeof(mark));
 84     dfn=bid=1;
 85     stop=0;
 86     for(int i=1; i<=n; ++i) if(mark[i]==0) dfs(i,-1);
 87 }
 88 
 89 Edge tredge[maxm];
 90 int trhead[maxn],tredgeNum;
 91 void addTrSubEdge(int u,int v)
 92 {
 93     tredge[tredgeNum].v=v;
 94     tredge[tredgeNum].next=trhead[u];
 95     trhead[u]=tredgeNum++;
 96 }
 97 void addTrEdge(int u,int v)
 98 {
 99     addTrSubEdge(u,v);
100     addTrSubEdge(v,u);
101 }
102 
103 int low2[maxn];
104 int mark2[maxn];
105 int dfn2;
106 void dfs2(int k,int p)
107 {
108     mark2[k]=low2[k]=dfn2++;
109     for(int i=head[k]; i!=-1; i=edge[i].next)
110     {
111         int j=edge[i].v;
112         if(j==p) continue;
113         if(mark2[j]==0)
114         {
115             dfs2(j,k);
116             low2[k]=min(low2[k],low2[j]);
117             if(low2[j]==mark2[j])
118             {
119                 addTrEdge(bcc[k],bcc[j]);
120                 //发现(k,j)为桥
121             }
122         }
123         else low2[k]=min(low2[k],mark2[j]);
124     }
125 }
126 void bridge()
127 {
128     memset(mark2,0,sizeof(mark2));
129     dfn2=1;
130     for(int i=1;i<=n;i++) if(mark2[i]==0) dfs2(i,-1);
131 }
132 
133 void init()
134 {
135     memset(head,-1,sizeof(head));
136     edgeNum=0;
137     memset(trhead,-1,sizeof(trhead));
138     tredgeNum=0;
139 }
140 void input()
141 {
142     scanf("%d%d",&n,&m);
143     for(int i=0;i<m;i++)
144     {
145         int u,v;
146         scanf("%d%d",&u,&v);
147         addEdge(u,v);
148     }
149 }
150 void solve()
151 {
152     tarjan();
153 //    for(int i=1;i<=n;i++) cout<<bcc[i]<<" ";
154 //    cout<<endl;
155 //    cout<<bid<<endl;
156     if(bid<=2)
157     {
158         puts("0");
159         return;
160     }
161     bridge();
162     int ans=0;
163     for(int i=1;i<bid;i++)
164     {
165         int cnt=0;
166         for(int j=trhead[i];j!=-1;j=tredge[j].next,cnt++);
167         if(cnt==1) ans++;
168     }
169     printf("%d
",(ans+1)/2);
170 }
171 int main()
172 {
173     std::ios_base::sync_with_stdio(false);
174 //    freopen("in.cpp","r",stdin);
175     init();
176     input();
177     solve();
178     return 0;
179 }
View Code