Cod sursa(job #680933)

Utilizator avram_florinavram florin constantin avram_florin Data 16 februarie 2012 10:39:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>

using namespace std;

const int MaxN = 100001;
const char InFile[] = "biconex.in";
const char OutFile[] = "biconex.out";

int N,M,nrc,nod1,nod2,lvl[MaxN],viz[MaxN],Last[MaxN];
vector<int> G[MaxN],sol[MaxN];
stack< pair<int,int> > St;

int minim(int x,int y)
{
	return x > y?y:x;
}

void DFS(int nod,int father)
{
	viz[nod] = 1;
	Last[nod] = lvl[nod];
	vector<int>::iterator it,iend;
	iend = G[nod].end();
	for( it = G[nod].begin() ; it != iend ; ++it )
		{
			int fiu = *it;
			if( !viz[fiu] )
				{
					lvl[fiu] = lvl[nod] + 1;
					St.push(make_pair(nod,fiu));
					DFS(fiu,nod);
					Last[nod] = minim(Last[nod],Last[fiu]);
					if( Last[fiu] >= lvl[nod] )
						{
							++nrc;
							do
							{
								nod1 = St.top().first;
								nod2 = St.top().second;
								St.pop();
								sol[nrc].push_back(nod1);
								sol[nrc].push_back(nod2);
							}
							while( ( nod1 != nod || nod2 != fiu ) && (nod1 != fiu || nod2 != nod) );
						}
				}
				else
				if( fiu != father )
					Last[nod] = minim(Last[nod],lvl[fiu]);
		}
}
int main()
{
	ifstream fin(InFile);
	ofstream fout(OutFile);
	fin >> N >> M;
	int i,x,y;
	for( int i = 0 ; i < M ; i++ )
		{
			fin >> x >> y;
			G[x].push_back(y);
			G[y].push_back(x);
		}
	fin.close();
	lvl[1] = 1;
	DFS(1,1);
	fout << nrc << '\n';
	for( i = 1; i <= nrc ; i++ )
		{
			sort(sol[i].begin(),sol[i].end());
			vector<int>::iterator it,iend;
			iend = sol[i].end();
			for( it = sol[i].begin() ; it != iend ; ++it )
				if( it == sol[i].begin() || *it != (*(it-1)) )
					fout << *it << ' ';
			fout << '\n';
		}
	fout.close();
	return 0;
}