Cod sursa(job #2131973)

Utilizator mariastStoichitescu Maria mariast Data 15 februarie 2018 11:10:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<cstdio>
#include<vector>
using namespace std;

int n,m,x,y,nr,l,k;
vector<int>g[100010];
vector<int>sol[100010];
int v1[100010],v2[100010],st[100010];
bool viz[100010];
void dfs(int x){
    nr++;
    viz[x]=1;
    v1[x]=v2[x]=nr;
    st[++k]=x;
    for(int i=0;i<g[x].size();++i){
        if(!viz[g[x][i]]){
            int ct=k;
            dfs(g[x][i]);
            v2[x]=min(v2[x],v2[g[x][i]]);
            if(v2[g[x][i]]>=v1[x]){
                ++l;
                while(k>ct)sol[l].push_back(st[k--]);
                sol[l].push_back(x);
            }
        }
        else{
            v2[x]=min(v2[x],v1[g[x][i]]);
        }

    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    printf("%d\n",l);
    for(int i=1;i<=l;++i){
        for(int j=0;j<sol[i].size();j++){
            printf("%d ",sol[i][j]);
        }
        printf("\n");
    }
}