Cod sursa(job #710728)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 10 martie 2012 17:26:08
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<fstream>
using namespace std;
#define lung 100001
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct nod{int val;
           nod *next;
};
nod *v[lung],*transp[lung],*rasp[lung];
bool pluss[lung],minu[lung],frecv[lung];
inline void bf1(int x)
{nod *q=v[x];
	if (q)
		if (!pluss[q->val])
	    	while(q)
	        {   pluss[q->val] = true;
                bf1(q->val);
    		    q = q -> next;
    		}
}
inline void bf2(int x)
{nod *q=transp[x];
	if (q)
        if (!minu[q->val])
	        while(q)
	        {   minu[q->val] = true;
			    bf2(q->val);
		        q = q -> next;
	        }
}
int main()
{nod *q; 
 int i,n,m,a,b,nr=0,j;
    fin >> n >> m;
    for (i=1;i<=m;++i)
    {   fin >> a >> b;
		q = new nod;
	    q -> next = v[a];
		q -> val = b;
		v[a] = q;
		q = new nod;
	    q -> next = transp[b];
		q -> val = a;
		transp[b] = q;
	}
	for (i=1;i<=n;++i)
	    if (!frecv[i])
		{   pluss[i] = true;
	        minu[i] = true;
         	bf1(i);
     	    bf2(i);
    	    ++nr;
			for (j=1;j<=n;++j)
	    	    if (pluss[j] && minu[j])
		        {	q = new nod;
					q -> val = j;
					q -> next = rasp[nr];
					rasp[nr] = q;
			        frecv[j] = true;
			    }
			for (j=1;j<=n;++j)
				pluss[j] = minu[i] = false;
	    }
	fout << nr << '\n';
	for (i=1;i<=nr;++i)
	{   q = rasp[i];
	    while (q)
		{   fout << q->val << " ";
		    q = q->next;
		}
		fout << '\n';
	}
	return 0;
}