首页 > itarticle > ural-1077. travelling tours

ural-1077. travelling tours

admin 11月 11, 2020 0

题意：

给定一 n 个节点 m 条边的图，求出来环的个数最大，且每个环点的个数大于2,环 i 与其他 T-1 个环
至少有一条边不一样。

分析：

n 个点 m 条边 p 个联通分量的图含有的环的个数是 m-n+p。先 dfs 求出来联通分量的个数，然后递归
输出即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N=205;
vector<int> g[N];
int n,m;
int stack[N],lev[N];
bool vis[N];
int top;
void dfs(int u) {
    if(vis[u]) return;
    vis[u]=1;
    for(int i=0;i<(int)g[u].size();i++) {
        int v=g[u][i];
        dfs(v);
    }
}
void print(int u) {
    stack[++top]=u;
    lev[u]=top;vis[u]=1;
    for(int i=0;i<(int)g[u].size();i++) {
        int v=g[u][i];
        if(!vis[v]) print(v);
        else {
            if(lev[u]-lev[v]>1) {
                cout<<lev[u]-lev[v]+1;
                for(int i=lev[v];i<=lev[u];i++) {
                    cout<<' '<<stack[i];
                }
                cout<<endl;
            }
        }
    }
    top--;
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int tmp=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) {
        if(!vis[i]) dfs(i),tmp++;
    }
    cout<<m-n+tmp<<endl;
    memset(vis,0,sizeof(vis));
    top=0;
    for(int i=1;i<=n;i++) {
        if(!vis[i]) print(i);
    }
    return 0;
}