Cod sursa(job #1252027)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 30 octombrie 2014 11:50:37
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <utility>
#include <set>

#define NMAX 100005
using namespace std;

vector<int> graf[NMAX];
int h[NMAX];
int low[NMAX];
bitset<NMAX> viz;

stack<pair<int,int> > stiva;
vector<set<int> > Set;

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();

    Set.push_back(nou);
}

void dfs(int nod,int father){
    viz[nod]=1;
    h[nod]=h[father]+1;
    low[nod]=h[nod];

    for(vector<int>::iterator it=graf[nod].begin();it!=graf[nod].end();it++)
        if(!viz[*it]){
            stiva.push(make_pair(nod,*it));
            dfs(*it,nod);
            low[nod]=min(low[nod],low[*it]);

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

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

    int n=0,m=0;
    cin>>n>>m;

    int a=0,b=0;
    while(m--){
        cin>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

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

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

    for(it=Set.begin();it!=Set.end();it++){
        cout<<*it->begin();

        it2=it->begin();it2++;
        for(;it2!=it->end();it2++)
            cout<<' '<<*it2;

        cout<<'\n';
    }

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