Cod sursa(job #2238297)

Utilizator Eric@Bangheorghe George Eric Eric@ Data 5 septembrie 2018 10:53:27
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

const int NMAX=100005;

int g=0,cnt;
int rootChildren,dfsRoot;

struct muchie{
    int u,v;
}aux;

vector <int> G[NMAX];
vector <int> sol[NMAX];
int idx[NMAX],low[NMAX],parent[NMAX];
int ap[NMAX];
stack <muchie> st;

void dfs(int u){
    ++g;
    idx[u]=low[u]=g;
    for(int i=0; i<G[u].size(); ++i){
        int v=G[u][i];
        if(idx[v]==0){
            aux.u=u;
            aux.v=v;
             st.push(aux);
            parent[v]=u;
            dfs(v);
            if(low[v]>=idx[u]){
                ap[u]=1;
                cnt++;
                while(st.top().u!=u || st.top().v!=v){
                    sol[cnt].push_back(st.top().v);
                    st.pop();
                }
                sol[cnt].push_back(u);
            }
            low[u]=min(low[v],low[u]);
        }
        else{
            if(v!=parent[u]){
                low[u]=min(low[u],idx[v]);
            }
        }
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int n,m;
    int u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;++i){
        if(idx[i]==0){
            dfsRoot=i; rootChildren=0;
            dfs(i);
            if(rootChildren>1){
                while(!st.empty()){
                    sol[cnt].push_back(st.top().u);
                    st.pop();
                }
                sol[cnt].push_back(i);
            }
            else
                ap[i]=0;
        }
    }
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;++i){
        for(int j=sol[i].size()-1;j>=0;--j)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
    return 0;
}