Cod sursa(job #1136209)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 8 martie 2014 22:06:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <set>

using namespace std;

#define MAXN 100005
#define pb push_back

vector<int> graf[MAXN];
int h[MAXN];
int low[MAXN];
bitset<MAXN> viz;
stack<pair<int,int> > stiva;
vector<set<int> > comp;

void scoate(int x,int y)
{
    set<int> nou;
    while(!stiva.empty() && (stiva.top().first!=x || stiva.top().second!=y))
    {
        nou.insert(stiva.top().first);
        nou.insert(stiva.top().second);
        stiva.pop();
    }

    nou.insert(stiva.top().first);
    nou.insert(stiva.top().second);
    stiva.pop();

    comp.push_back(nou);
}

void dfs(int nod,int father)
{
    low[nod]=h[nod];
    vector<int>::iterator it;
    for(it=graf[nod].begin();it!=graf[nod].end();it++)
        if(!viz[*it])
        {
            viz[*it]=1;
            h[*it]=h[nod]+1;

            stiva.push(make_pair(nod,*it));
            dfs(*it,nod);

            low[nod]=min(low[nod],low[*it]);

            if(h[nod]<=low[*it])
                scoate(nod,*it);
        }
        else if(*it!=father)
            low[nod]=min(low[nod],h[*it]);
}

int main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");

    int n=0,m=0,i,a,b;
    cin>>n>>m;

    for(i=0;i<m;i++)
    {
        cin>>a>>b;
        graf[a].pb(b);
        graf[b].pb(a);
    }

    for(i=1;i<=n;i++)
        if(!viz[i])
        {
            h[i]=1;
            viz[i]=1;
            dfs(i,0);
        }

    vector<set<int> >::iterator it;
    set<int>::iterator it2;

    cout<<comp.size()<<'\n';
    for(it=comp.begin();it!=comp.end();it++)
    {
        for(it2=it->begin();it2!=it->end();it2++)
            cout<<*it2<<' ';
        cout<<'\n';
    }

    cin.close();
    cout.close();
    return 0;
}