Cod sursa(job #875635)

Utilizator enedumitruene dumitru enedumitru Data 10 februarie 2013 15:47:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream> 
#include <stack> 
#include <vector> 
#include <algorithm> 
#define pb push_back
#define Nmax  100005  
using namespace std; 
ifstream f("biconex.in"); ofstream g("biconex.out");
int n,m,x,y;  
vector <int> adj[Nmax], d(Nmax,-1), low(Nmax); 
vector <vector <int> > C; 
stack <pair <int, int> > stk; 
void CompTC(const int x, const int y) 
{   vector <int> con; 
	int ei,ef; 
    do 
	{   ei=stk.top().first, ef=stk.top().second; stk.pop(); 
        con.pb(ei); con.pb(ef); 
    } 
    while(ei!=x || ef!=y); 
    C.pb(con); 
} 
void DFS(const int n, const int fn, int number) 
{   d[n]=low[n]=number; 
	vector <int> :: iterator it=adj[n].begin(), sf=adj[n].end(); 
    for (; it!=sf ; ++it) 
	{   if (*it == fn) continue ; 
        if (d[*it] == -1) 
		{   stk.push(make_pair(n,*it)); 
            DFS(*it,n,number+1); 
            low[n]=min(low[n],low[*it]); 
            if (low[*it]>=d[n]) CompTC(n,*it); 
        } 
        else low[n]=min(low[n],d[*it]); 
    } 
} 
int main(void) 
{   f>>n>>m; 
    while(m--) {f>>x>>y; adj[x].pb(y); adj[y].pb(x);} 
    DFS(1,0,0); 
    g<<C.size()<<"\n"; 
    for(unsigned int i=0; i<C.size(); ++i) 
	{   sort(C[i].begin(),C[i].end()); 
        C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end()); 
        for (unsigned int j=0; j<C[i].size(); ++j) g<<C[i][j]<<" "; 
        g<<"\n"; 
    } 
    g.close(); return 0; 
}