Cod sursa(job #1768360)

Utilizator tavonSuleyman Magnificul tavon Data 30 septembrie 2016 19:35:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int Nmax = 100001;
vector<int> G[Nmax],Comp[Nmax];
int m[Nmax],st[Nmax];
int N,M,K,C;

void dfs(int x,int d,int t){
    m[x]=d;
    st[++K]=x;
    for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++){
        if(!m[*it]){
            int mk=K;
            dfs(*it,d+1,x);
            if(m[*it]>=d){
                C++;
                while(K!=mk) Comp[C].push_back(st[K--]);
                Comp[C].push_back(x);
            }
        }
        if(*it!=t) m[x]=min(m[x],m[*it]);
    }
}

int main(){
    in>>N>>M;
    int a,b;
    for(int i=1;i<=M;i++) in>>a>>b,G[a].push_back(b),G[b].push_back(a);
    dfs(1,1,0);
    out<<C<<'\n';
    for(int i=1;i<=C;i++){
        for(auto it : Comp[i]){
            out<<it<<' ';
        }
        out<<'\n';
    }
    return 0;
}