Cod sursa(job #613041)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 15 septembrie 2011 10:36:56
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<fstream>
#include<vector>
#define inf 100000

using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

vector<int> graph[inf];
int n,m,nv[inf],low[inf],t[inf],ras[inf],u[inf],rad,nr;
void df(int nod)
{
    u[nod]=1;
    low[nod]=nv[nod];
    for(int i=0;i<graph[nod].size();i++)
    {
        int child=graph[nod][i];
        if(u[child]!=1)
        {
            t[child]=nod;
            nv[child]=nv[nod]+1;
            if(nod==rad)nr++;
            df(child);
            if(low[child]<low[nod]) low[nod]=low[child];
            if(low[child]>=nv[nod]) ras[nod]=1;
        }
        else if(child!=t[nod]&&low[nod]>=nv[child]) low[nod]=nv[child];
    }
}

int main()
{
    in >> n >>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        inf >> x >>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
    {
        if(u[i]!=1)
        {
           nv[i]=1;
           rad =i;
           nr=0;
           df(i);
           if(nr>1)ras[rad]=1;
        }
    }

    int nrras=0;
    for(int i=1;i<=n;i++) if(ras[i]==1)nrras++;

    out << nrras <<'\n';

    for(int i=1;i<=n;i++) if(ras[i]==1)
    {
        out <<i<<' ';
        for(int j=0;j<graph[i].size();j++)out<<graph[i][j]<<' ';
        out<<'\n';
    }


}