【HDU3394】Railway

【题目描述】

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

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

【题解】

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

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<ctime>

 #include<algorithm>

 using namespace std;

 #define MAXN 10010

 struct node{int y,next;}e[];

 int n,m,ans1,ans2,len,top,dfs_clock,bcnt,belong[MAXN],Link[MAXN],dfn[MAXN],low[MAXN],stack[MAXN],vis[MAXN];

 inline int read()

 {

     int x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 void insert(int x,int y) {e[++len].next=Link[x];Link[x]=len;e[len].y=y;}

 void pre()

 {

     ans1=ans2=len=top=dfs_clock=;

     memset(Link,,sizeof(Link));

     memset(dfn,,sizeof(dfn));

 }

 void count()

 {

     int sum=;

     for(int i=;i<=bcnt;i++)

     {

         int x=belong[i];

         for(int j=Link[x];j;j=e[j].next)

             if(vis[e[j].y])  sum++;

     }

     sum/=;

     if(sum>bcnt)  ans2+=sum;

 }

 void tarjan(int x,int father)

 {

     dfn[x]=low[x]=++dfs_clock;

     stack[++top]=x;

     for(int i=Link[x];i;i=e[i].next)

     {

         if(e[i].y==father)  continue;

         if(!dfn[e[i].y])

         {

             tarjan(e[i].y,x);

             low[x]=min(low[x],low[e[i].y]);

             if(low[e[i].y]>dfn[x])  ans1++;

             if(low[e[i].y]>=dfn[x])

             {

                 int y; bcnt=;

                 memset(vis,,sizeof(vis));

                 do

                 {

                     y=stack[top--];

                     vis[y]=;

                     belong[++bcnt]=y;

                 }while(e[i].y!=y);

                 belong[++bcnt]=x;

                 vis[x]=;

                 count();

             }

         }

         else low[x]=min(low[x],dfn[e[i].y]);

     }

 }

 void solve()

 {

     for(int i=;i<n;i++)  if(!dfn[i])  tarjan(i,-);

     printf("%d %d\n",ans1,ans2);

 }

 int main()

 {

     //freopen("cin.in","r",stdin);

     //freopen("cout.out","w",stdout);

     while(scanf("%d%d",&n,&m)==)

     {

         if(n==&&m==)  break;

         pre();

         for(int i=;i<=m;i++)  {int x=read(),y=read();  insert(x,y);  insert(y,x);}

         solve();

     }

     return ;

 }

巴特西

【HDU3394】Railway

最新文章

热门文章