Cod sursa(job #1647302)

Utilizator gabib97Gabriel Boroghina gabib97 Data 10 martie 2016 19:54:00
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
int n,m,i,h[100001],d[100001],t[100001],x,y,nr,j;
bool o[100001],pa[100001];
vector<int> G[100001],r[100001];
stack<int> Q;
void afis(int s)
{
    int x;
    ++nr;
    x=Q.top();
    while (x!=s)
    {
        r[nr].push_back(x);
        Q.pop();
        x=Q.top();
    }
    r[nr].push_back(x);
}
void DFS(int s)
{
    int i,z=G[s].size();
    o[s]=1;
    d[s]=h[s];
    Q.push(s);
    for (i=0;i<z;i++)
        if (!o[G[s][i]])
    {
        t[G[s][i]]=s;
        h[G[s][i]]=h[s]+1;
        DFS(G[s][i]);
        d[s]=min(d[s],d[G[s][i]]);
        if (d[G[s][i]]>=h[s]) afis(s);
    }
    else if (G[s][i]!=t[s]) d[s]=min(d[s],h[G[s][i]]);
}
int main()
{
    freopen ("biconex.in","r",stdin);
    freopen ("biconex.out","w",stdout);
    scanf("%i%i",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%i%i",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for (i=1;i<=n;i++)
        if (!o[i]) DFS(i);
    printf("%i",nr);
    for (i=1;i<=nr;i++)
    {
        printf("\n");
        for (j=0;j<r[i].size();j++) printf("%i ",r[i][j]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}