【HDU3394】Railway

【题目描述】

有一个公园有n个景点，公园的管理员准备修建m条道路，并且安排一些形成回路的参观路线。如果一条道路被多条道路公用，那么这条路是冲突的；如果一条道路没在任何一个回路内，那么这条路是不冲突的

问分别有多少条有冲突的路和没有冲突的路

【题解】

这是一道点双联通的题，首先把图缩成块，显然如果块中边的数量大于点的数量，那么块中所有的边都是冲突的。

对于没有冲突的边，其实就是桥，tarjan的时候顺便求一下就行了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<ctime>
 7 #include<algorithm>
 8 using namespace std;
 9 #define MAXN 10010
10 struct node{int y,next;}e[200010];
11 int n,m,ans1,ans2,len,top,dfs_clock,bcnt,belong[MAXN],Link[MAXN],dfn[MAXN],low[MAXN],stack[MAXN],vis[MAXN];
12 inline int read()
13 {
14     int x=0,f=1;  char ch=getchar();
15     while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
16     while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
17     return x*f;
18 }
19 void insert(int x,int y) {e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
20 void pre()
21 {
22     ans1=ans2=len=top=dfs_clock=0;
23     memset(Link,0,sizeof(Link));
24     memset(dfn,0,sizeof(dfn));
25 }
26 void count()
27 {
28     int sum=0;
29     for(int i=1;i<=bcnt;i++)
30     {
31         int x=belong[i];
32         for(int j=Link[x];j;j=e[j].next)
33             if(vis[e[j].y])  sum++;
34     }
35     sum/=2;
36     if(sum>bcnt)  ans2+=sum;
37 }
38 void tarjan(int x,int father)
39 {
40     dfn[x]=low[x]=++dfs_clock;
41     stack[++top]=x;
42     for(int i=Link[x];i;i=e[i].next)
43     {
44         if(e[i].y==father)  continue;
45         if(!dfn[e[i].y])
46         {
47             tarjan(e[i].y,x);
48             low[x]=min(low[x],low[e[i].y]);
49             if(low[e[i].y]>dfn[x])  ans1++;
50             if(low[e[i].y]>=dfn[x])
51             {
52                 int y; bcnt=0;
53                 memset(vis,0,sizeof(vis));
54                 do
55                 {
56                     y=stack[top--];
57                     vis[y]=1;
58                     belong[++bcnt]=y;
59                 }while(e[i].y!=y);
60                 belong[++bcnt]=x;
61                 vis[x]=1;
62                 count();
63             }
64         }
65         else low[x]=min(low[x],dfn[e[i].y]);
66     }
67 }
68 void solve()
69 {
70     for(int i=0;i<n;i++)  if(!dfn[i])  tarjan(i,-1);
71     printf("%d %d
",ans1,ans2);
72 }
73 int main()
74 {
75     //freopen("cin.in","r",stdin);
76     //freopen("cout.out","w",stdout);
77     while(scanf("%d%d",&n,&m)==2)
78     {
79         if(n==0&&m==0)  break;
80         pre();
81         for(int i=1;i<=m;i++)  {int x=read(),y=read();  insert(x,y);  insert(y,x);}
82         solve();
83     }
84     return 0;
85 }