Cod sursa(job #511777)

Utilizator liviumlivica livium Data 12 decembrie 2010 22:25:40
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.57 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <string>

using namespace std;

class Vertex {
  
private:
  int nod;
  int pre;

public:
	Vertex() { nod=-1; pre=-1;}
       
    Vertex(int nodd, int pree) { nod=nodd; pre=pree; }

  int get_nod() const  { return nod; }
  int get_pre()  const { return pre; }
  void set_pre(int pree) {pre=pree;}

 bool operator==(const Vertex &other)  const { return (this->get_nod()==other.get_nod()); }
 bool operator!=(const Vertex &other)  const { return (this->get_nod()!=other.get_nod()); }

};


vector<vector<int>> ll; vector<int> ln;  Vertex* noduri; int c=0; stack<Vertex> S,P;
int n,m;   vector<vector<int>> a;  vector<int> l; 

void add(int i, int j)
{
	ll[i].push_back(j);

}
void initializare_lista(int n)
{
	for (int i=0; i<=n-1; i++)	ll.push_back(ln);
	
}

void initializare()
{
	ifstream fis;
	fis.open("ctc.in");
	
	fis>>n;	fis>>m;

	if (!(n>=1 && n<=100000 && m>=1 && m<=200000)) return;	
	
	noduri=new Vertex[n];

	for (int i=0; i<=n-1; i++) noduri[i]=Vertex(i,-1);

	initializare_lista(n);

    int i=1,a,b;
	while (i<=m)
	{
		fis>>a;
		fis>>b;
		add(a-1,b-1);

		++i;
	}

}

bool exista(vector<vector<int>> a, int nod)
{
	for (size_t i=0; i<a.size(); i++)
		for (size_t j=0; j<a[i].size(); j++)
			if (a[i][j]==nod) return true;

	return false;
}

bool e_vecin(int lni, int col)
{
	for (size_t j=0; j<ll[lni].size(); j++)
			if (ll[lni][j]==col) return true;

return false;
}

void gabow(Vertex ver)
{
	ver.set_pre(c); 
	noduri[ver.get_nod()].set_pre(c);
	++c; 
	S.push(ver); P.push(ver);

		for (int i=0; i<=n-1; i++)
			if (e_vecin(ver.get_nod(),i))
			{
				if (noduri[i].get_pre()==-1) gabow(noduri[i]);
				 else 
					if (!exista(a,i))
					{
						Vertex vr=P.top();
						while(vr.get_pre() > noduri[i].get_pre())
						  {
							P.pop();
							vr=P.top();
						  }
					}
			 }

	if (ver==P.top())
	{
		Vertex vr;
		do
		{
			vr=S.top();
			l.push_back(vr.get_nod());
			S.pop();
		}
		while(vr!=ver);

	a.push_back(l);
	l.clear();
	P.pop();
	}

}

void dfs()
{
	for (int i=0; i<=n-1; i++)
		if (noduri[i].get_pre()==-1) 
			gabow(noduri[i]);

}

void afisare_scc()
{
	ofstream fis;
	fis.open("ctc.out");
	
	fis<<a.size()<<endl;
	for (size_t i=0; i<a.size(); i++)
	{
		for (size_t j=0; j<a[i].size(); j++)
		   		fis<<a[i][j]+1<<" ";
	fis<<endl;
	}
}

int main()
{
	initializare();
	if (n>=1 && n<=100000 && m>=1 && m<=200000)
	{
		dfs();
		afisare_scc();
	}
return 0;
}