题面：

4116: [Wf2015]Tours

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 129  Solved: 46

[][][]

Description

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

Input

第一行两个正整数n,m接下来m行，每行两个正整数x,y(1<=x
     
      <=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

Sample Output

1 3

HINT

 n,m<=2000

 

我们先将边集分为若干个子集,满足每个简单环都可以有这些子集相加得到,答案就是这些子集大小$gcd$的约数。

对于一个简单环,它上面的边一定不是桥边,而且不在其他简单环上,所以我们枚举每一条桥边,把它删去,之后统计变成桥边的边的个数。

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5 using namespace std;  6 #define maxn 2010  7 struct edge  8 {  9     int u,v,id,nex; 10 }e[maxn<<1]; 11 int pr[maxn],cnt=1; 12 int from[maxn],to[maxn]; 13 inline void add(int u,int v,int w) 14 { 15     e[++cnt]=(edge){u,v,w,pr[u]}; 16     pr[u]=cnt; 17     e[++cnt]=(edge){v,u,w,pr[v]}; 18     pr[v]=cnt; 19 } 20 inline int read() 21 { 22     int s=0,f=1; 23     char ch=getchar(); 24     while(ch<'0'||ch>'9') 25     { 26         if(ch=='-') 27             f=-1; 28         ch=getchar(); 29     } 30     while(ch>='0'&&ch<='9') 31         s=s*10+ch-'0',ch=getchar(); 32     return s*f; 33 } 34 int low[maxn],dfn[maxn]; 35 int scc_dfn; 36 bool bridge[maxn],vis[maxn],rem[maxn]; 37 void tarjan(int u,int E) 38 { 39     low[u]=dfn[u]=++scc_dfn; 40     for(int i=pr[u];i;i=e[i].nex) 41     { 42         if(i^E^1) 43         { 44             int v=e[i].v; 45             if(dfn[v]) 46                 low[u]=min(low[u],dfn[v]); 47             else 48             { 49                 tarjan(v,i); 50                 low[u]=min(low[u],low[v]); 51                 if(low[v]>dfn[u]) 52                     bridge[e[i].id]=true; 53             } 54         } 55     } 56 } 57 inline void init() 58 { 59     scc_dfn=0;cnt=1; 60     memset(pr,0,sizeof(pr)); 61     memset(low,0,sizeof(low)); 62     memset(dfn,0,sizeof(dfn)); 63     memset(bridge,0,sizeof(bridge)); 64 } 65 int n,m; 66 int main() 67 { 68     n=read(); 69     m=read(); 70     int u,v; 71     for(int i=1;i<=m;i++) 72     { 73         from[i]=read(); 74         to[i]=read(); 75         add(from[i],to[i],i); 76     } 77     for(int i=1;i<=n;i++) 78         if(!dfn[i]) 79             tarjan(i,0); 80     memcpy(rem,bridge,sizeof(bridge)); 81     int ans=0; 82     for(int i=1;i<=m;i++) 83     { 84         int tot=1; 85         if(rem[i]||vis[i]) 86             continue; 87         init(); 88         for(int j=1;j<=m;j++) 89             if(j!=i) 90                 add(from[j],to[j],j); 91         for(int i=1;i<=n;i++) 92             if(!dfn[i]) 93                 tarjan(i,0); 94         for(int j=1;j<=m;j++) 95             if(!rem[j]&&bridge[j]) 96                 vis[j]=true,++tot; 97         ans=__gcd(ans,tot); 98     } 99     for(int i=1;i<=ans;i++)100         if(ans%i==0)101         {102             printf("%d",i);103             if(i!=ans)104                 putchar(' ');105         }106 }