Cod sursa(job #500997)

Utilizator skullLepadat Mihai-Alexandru skull Data 13 noiembrie 2010 23:52:41
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<stdio.h>
#include<vector>
#include <algorithm>
using namespace std;
#define nmax 1005

int n, m, nr, nrsol;
struct punct
{
    int x, y;
}st[nmax*nmax];
vector<int> G[nmax], sol[nmax], vec;
int lvl[nmax], c[nmax], viz[nmax];

void citire()
{
	freopen("kgb.in","r",stdin);
    scanf("%d",&n);
    int x, y;
    while ( !feof(stdin) )
    {
        scanf("%d %d ", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void add(int x, int y)
{
    nrsol++;
	vec.push_back(x);
    do{
        sol[nrsol].push_back(st[nr].y);
        nr--;
    }while(st[nr+1].x!=x || st[nr+1].y!=y);
    sol[nrsol].push_back(st[nr+1].x);
	sort ( sol[nrsol].begin(), sol[nrsol].end() ); 
}

void dfs(int nod,int tata)
{
	int i, x;
    lvl[nod] = lvl[tata] + 1;
    c[nod] = lvl[nod];
    viz[nod] = 1;
    for( i = 0; i < G[nod].size(); ++i)
    {
        x = G[nod][i];
        if( !viz[x] )
        {
            st[++nr].x=nod;
            st[nr].y=x;
            dfs(x, nod);
            if(c[x]<c[nod])
                c[nod]=c[x];
            if(c[x] >= lvl[nod])
                add(nod,x);
        }
        else if(tata!=x && c[x]<c[nod])
            c[nod]=c[x];
    }
}

void afisare()
{
	int i, j;
	freopen("kgb.out","w",stdout);
    if (nrsol == 1)
		printf("KGB este forte");
	else
	{
		printf("KGB nu este forte\n");
		sort(vec.begin(), vec.end() );
		for (i = 0; i < vec.size (); ++i) if (vec[i]!=vec[i-1]) printf("%d ", vec[i]);
		printf("\n%d \n", nrsol);
		for(i = 1; i <= nrsol;++i)
		{
			for(j = 0; j < sol[i].size(); ++j)
				printf("%d ",sol[i][j]);
			printf("\n");
		}
	}
}

int main()
{
    citire ();
    dfs (0,0);
    afisare ();
    return 0;
}