Cod sursa(job #1408789)

Utilizator gabib97Gabriel Boroghina gabib97 Data 30 martie 2015 11:28:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
int n,m,i,x,y,niv[100001],j[100001],t,T[100001];
bool o[100001];
int k;
vector<int> G[100001],c[100001];
stack<pair<int,int> > stiva;
void afis(int a,int b)
{
    t++;
    pair<int,int> p=stiva.top();
    while (p.first!=a||p.second!=b)
    {
        c[t].push_back(p.second);
        stiva.pop();
        p=stiva.top();
    }
    stiva.pop();
    c[t].push_back(b);
    c[t].push_back(a);
}
void DFS(int s)
{
    int i,z=G[s].size();
    o[s]=1; j[s]=niv[s];
    for (i=0;i<z;i++)
        if (!o[G[s][i]])
    {
        niv[G[s][i]]=niv[s]+1;
        stiva.push(make_pair(s,G[s][i]));
        T[G[s][i]]=s;
        DFS(G[s][i]);
        j[s]=min(j[s],j[G[s][i]]);
        if (j[G[s][i]]>=niv[s]) afis(s,G[s][i]);
    }
    else if (G[s][i]!=T[s])
        j[s]=min(j[s],j[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);
    }
    DFS(1);
    printf("%i\n",t);
    for (i=1;i<=t;i++,printf("\n"))
        for (k=0;k<c[i].size();k++) printf("%i ",c[i][k]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}