Cod sursa(job #751676)

Utilizator ChallengeMurtaza Alexandru Challenge Data 26 mai 2012 17:00:22
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

ifstream fin(InFile);
ofstream fout(OutFile);

struct Edge
{
	Edge(int x=0, int y=0):x(x),y(y){}
	int x,y;
};

int N,M,x,y,niv[MaxN],low[MaxN];
vector<int> c,G[MaxN];
vector<vector<int>> C;
stack<Edge> S;

inline void Componenta(int x, int y)
{
	c.clear();
	Edge e;
	do
	{
		e=S.top();
		S.pop();
		c.push_back(e.y);
	}while(e.x!=x && e.y!=y);
	c.push_back(e.x);

	C.push_back(c);
}

void DFS(int nod, int t=0)
{
	low[nod]=niv[nod];
	for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
	{
		if(*it==t)
		{
			continue;
		}
		if(!niv[*it])
		{
			S.push(Edge(nod,*it));
			niv[*it]=niv[nod]+1;
			DFS(*it,nod);

			low[nod]=min(low[nod],low[*it]);
			if(low[*it]>=niv[nod])
			{
				Componenta(nod,*it);
			}
		}
		else
		{
			low[nod]=min(low[nod],low[*it]);
		}
	}
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	fin.close();

	for(register int i=1;i<=N;++i)
	{
		if(!niv[i])
		{
			niv[i]=1;
			DFS(i);
		}
	}

	fout<<C.size()<<"\n";
	for(vector<vector<int>>::iterator it=C.begin();it!=C.end();++it)
	{
		for(vector<int>::iterator it2=it->begin();it2!=it->end();++it2)
		{
			fout<<*it2<<" ";
		}
		fout<<"\n";
	}
	fout.close();
	return 0;
}