Cod sursa(job #282119)

Utilizator ScrazyRobert Szasz Scrazy Data 16 martie 2009 21:56:09
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

const int maxn = 100002;

int n;
vector<int> G[maxn];
vector<int> C[maxn];

int dfn[maxn], low[maxn];
bool viz[maxn];
int cached[maxn];

stack< pair<int, int> > S;

int res;

void read()
{
    int m;
    scanf("%d%d", &n, &m);
    for (; m; --m)
    {
	int x, y; scanf("%d%d", &x, &y);
	G[x].push_back(y);
	G[y].push_back(x);
    } 
}

void solve(int x, int tx)
{ 
    viz[x] = 1;
    low[x] = dfn[x];

    for (int i = 0; i < G[x].size(); ++i)
    {
	int next = G[x][i];
	if (tx == next) continue;

	if (!viz[next])
	{ 
	    dfn[next] = dfn[x] + 1; 
	    S.push(make_pair(x, next));
	    
	    solve(next, x);

	    low[x] = min(low[x], low[next]); 

	    if (low[next] >= dfn[x])
	    { 
		++res;

		int tx, tnext;
		do 
		{
		    tx = S.top().first; tnext = S.top().second;
		    S.pop();
		    if (cached[tx] != res)
		    {
			cached[tx] = res;
			C[res].push_back(tx);
		    }

		    if (cached[tnext] != res)
		    {
			cached[tnext] = res;
			C[res].push_back(tnext);
		    }
		}
		while (tx != x || tnext != next);

	    }
	}
	else low[x] = min(low[x], dfn[next]); 
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    read();
    solve(1, 0);

    printf("%d\n", res);

    for (int i = 1; i <= res; ++i)
    {
	for (int j = 0; j < C[i].size(); ++j) printf("%d ", C[i][j]);
	printf("\n");
    }

    return 0;
}