Cod sursa(job #1344533)

Utilizator rsteliRadu Stelian rsteli Data 16 februarie 2015 19:55:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");

#define nmax 100010
#define mp make_pair
#define pb push_back
#define forn(i,a,b) for (int i=a;i<=b;i++)
#define forv(v,it) for (vector<int>::iterator it=v.begin();it!=v.end();it++)

int n,m,x,y,nrc;
int dfn[nmax],low[nmax];
vector<int> g[nmax],c[nmax];
stack<pair<int,int> > a;

void cbc(int x,int y)
{
    int st,fi;
    nrc++;
    do
    {
        st=a.top().first;
        fi=a.top().second;
        c[nrc].pb(st);
        c[nrc].pb(fi);
        a.pop();
    }while (x!=st || y!=fi);
}

void dfs(int nod,int p,int num)
{
    dfn[nod]=low[nod]=++num;
    forv(g[nod],it)
    {
        if (*it==p) continue;
        if (!dfn[*it])
        {
            int t=*it;
            a.push(mp(nod,t));
            dfs(*it,nod,num);
            low[nod]=min(low[nod],low[*it]);
            if (low[*it]>=dfn[nod])
                cbc(nod,*it);
        }
        else low[nod]=min(low[nod],dfn[*it]);
    }
}

int main()
{
    cin>>n>>m;
    forn(i,1,m)
    {
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1,0,0);
    cout<<nrc<<'\n';
    forn(i,1,nrc)
    {
        sort(c[i].begin(),c[i].end());
        c[i].erase(unique(c[i].begin(),c[i].end()),c[i].end());
        forv(c[i],it)
            cout<<*it<<" ";
        cout<<'\n';
    }
}