Cod sursa(job #1869386)

Utilizator ImGeluGelu Ungur ImGelu Data 5 februarie 2017 19:37:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <vector>
#include <bitset>

#define maxN 100100

using namespace std;

//ifstream fin("ctc.in");
//ofstream fout("ctc.out");

vector <int> a[maxN], aTranspus[maxN], s[maxN], v;
int transpus[maxN], sol=0, k=0;
bitset <maxN> viz;

void dfs(int nod){
	viz[nod]=1;
 	for(int i=0; i<a[nod].size(); i++)
		if(!viz[a[nod][i]]) dfs(a[nod][i]);
		k++;
		transpus[nod]=k;
}

void dfsTranspus(int nod){
	s[sol].push_back(nod);
	viz[nod]=1;
	for(int i=0; i<aTranspus[nod].size(); i++)
		if(!viz[aTranspus[nod][i]]) dfsTranspus(aTranspus[nod][i]);
}

int main(){

    int n, m, x, y;

	cin>>n>>m;

	for(int i=1; i<=m; i++){
		cin>>x>>y;
		a[x].push_back(y);
		aTranspus[y].push_back(x);
	}

	for(int i=1; i<=n; i++)
		if(!viz[i]) dfs(i);

	for(int i=1; i<=n; i++) v.push_back(i);

	viz.reset();

	for(int i=0; i<n; ++i)
		if(!viz[v[i]]){ sol++; dfsTranspus(v[i]); }

    cout<<sol<<"\n"; ///afisarea numarului de solutii

	for(int i=1; i<=sol; i++){
		for(int j=0; j<s[i].size(); j++){
			cout<<s[i][j]<<" ";
		}
			cout<<endl;
    }

    return 0;
}