Cod sursa(job #622600)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 18 octombrie 2011 10:25:02
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define N 50010
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

int n,m,ordine[N],nrc,nr;
vector<int> g[N],ctc[N],gt[N];
bool vizitat[N];

void df_final(int nod) {
	vector<int>::iterator i;

	for(i=g[nod].begin();i!=g[nod].end();++i) if(!vizitat[*i]) {
		vizitat[*i]=true;
		df_final(*i);
	}

	ordine[++nr]=nod;
}

void df(int nod) {
	vector<int>::iterator i;

	vizitat[nod]=true;

	for(i=gt[nod].begin();i!=gt[nod].end();++i) if(!vizitat[*i]) {
		ctc[nrc].push_back(*i);
		df(*i);
	}
}

bool cmp(vector<int> a, vector<int> b) {
    vector<int>::iterator it;
    int min=1<<20,min2=1<<20;

    for(it=a.begin();it!=a.end();++it)
        if(*it<min)
            min=*it;

    for(it=b.begin();it!=b.end();++it)
        if(*it<min2)
            min2=*it;

    return min<min2;
}

int main() {
	int i,a,b;

	in >> n >> m;

	for(i=1;i<=m;++i) {
		in >> a >> b;

		g[a].push_back(b);
		gt[b].push_back(a);
	}

    for(i=1;i<=n;++i) if(!vizitat[i]) {

        vizitat[i]=true;
        df_final(i);
    }

	for(i=1;i<=n;++i)
		vizitat[i]=false;

	for(i=n;i!=0;--i) if(!vizitat[ordine[i]]) {
		++nrc;
		ctc[nrc].push_back(ordine[i]);
		df(ordine[i]);
	}

	out << nrc << "\n";

	vector<int>::iterator it;

    //sort(&ctc[1],&ctc[nrc+1],cmp);

	for(i=1;i<=nrc;++i) {



		for(it=ctc[i].begin();it!=ctc[i].end();++it)
			out << *it << " ";

		out << "\n";
	}

	return 0;
}