[Wf2015]Tours

题目

给定一张n个点m条边的无向图，你需要选择一个颜色种类数k，然后用这k种颜色给每条边染色，要求对于图中任意一个简单环，每种颜色的边的数量都相同，求所有可行的k

INPUT

第一行两个正整数n,m
接下来m行，每行两个正整数x,y(1<=x<y<=n)，代表一条无向边
数据保证无重边无自环

OUTPUT

一行输出所有可行的k,按递增顺序输出 6 6 1 2 2 3 1 3 1 4 2 5 3 6

SAMPLE

INPUT

6 6
1 2
2 3
1 3
1 4
2 5
3 6

OUTPUT

1 3

解题报告

其实这道题的关键在于找到每个简单环的边数，所以我们考虑如何处理简单环

显然，在一个简单环中，删去一条边，剩下的边就会变为割边

所以就可以得出做法：枚举原图非桥边，删去该边，处理出新增的桥边数量，所有数量+1的$GCD$所有的因数即为答案

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 inline int read(){

     int sum();char ch(getchar());

     for(;ch<''||ch>'';ch=getchar());

     for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());

     return sum;

 }

 int n,m,tot,ans(-);

 int dfn[],low[],cnt,tmp;

 int fro[],to[];

 bool bridge[],vis[];

 struct edge{

     int e,id;

     edge *n;

 }*pre[],a[];

 inline void insert(int s,int e,int id){

     a[++tot].e=e;

     a[tot].id=id;

     a[tot].n=pre[s];

     pre[s]=&a[tot];

 }

 inline void init(){

     memset(pre,NULL,sizeof(pre));

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

     tot=cnt=tmp=;

 }

 inline void tarjan(int u,int fa){

     dfn[u]=low[u]=++cnt;

     for(edge *i=pre[u];i;i=i->n){

         int e(i->e);if(e==fa)continue;

         if(!dfn[e]){

             tarjan(e,u);

             low[u]=min(low[u],low[e]);

             if(low[e]>dfn[u])bridge[i->id]=;

         }

         else low[u]=min(low[u],dfn[e]);

     }

 }

 inline void dfs(int u,int fa){

     dfn[u]=low[u]=++cnt;

     for(edge *i=pre[u];i;i=i->n){

         int e(i->e);if(e==fa)continue;

         if(!dfn[e]){

             dfs(e,u);

             low[u]=min(low[u],low[e]);

             if(low[e]>dfn[u]&&bridge[i->id]==)++tmp,vis[i->id]=;

         }

         else low[u]=min(low[u],dfn[e]);

     }

 }

 inline int gcd(int x,int y){

     return x%y?gcd(y,x%y):y;

 }

 int main(){

     n=read();m=read();

     for(int i=;i<=m;++i){

         int x(read()),y(read());

         fro[i]=x;to[i]=y;

         insert(x,y,i);insert(y,x,i);

     }

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

         if(!dfn[i])

             tarjan(i,);

     for(int i=;i<=m;++i){

         if(bridge[i]||vis[i])continue;

         init();

 //      for(int j=1;j<=m;++j)cout<<j<<' '<<bridge[j]<<endl;cout<<endl;//cout<<"ban "<<i<<endl;

         for(int j=;j<=m;++j)

             if(j^i){//cout<<j<<' '<<fro[j]<<' '<<to[j]<<endl;

                 insert(fro[j],to[j],j);

                 insert(to[j],fro[j],j);

             }

         for(int j=;j<=n;++j)

             if(!dfn[j])

                 dfs(j,);

 //      for(int j=1;j<=m;++j)cout<<j<<' '<<bridge[j]<<endl;cout<<endl;

         if(ans==-)ans=tmp+;

         else ans=gcd(ans,tmp+);

 //      cout<<tmp<<' '<<ans<<endl;

     }

 //  cout<<ans<<endl;

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

         if(ans%i==){

             printf("%d",i);

             if(i^ans)putchar(' ');

         }

 }

巴特西

[Wf2015]Tours

[Wf2015]Tours

题目

INPUT

OUTPUT

SAMPLE

INPUT

OUTPUT

解题报告

最新文章

热门文章