Cod sursa(job #1891052)

Utilizator wilson182Alexandrina Panfil wilson182 Data 23 februarie 2017 18:28:35
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<bits/stdc++.h>
#define N 100020
using namespace std;
int n,  k=0;
int v[N], c[N];
vector <int> sl,  lda[N], lds[N]; 
vector <vector<int> >sol;
void dfs(int nod){
	v[nod]=1;
	int i, l;
	l=lda[nod].size();
	for(i=0;i<l;i++){
		int x=lda[nod][i], y;
		if(!v[x]){
		dfs(x);
	} 
	}
	c[++k]=nod;
}
void dfs1(int nod){
	int i, l;
	v[nod]=2;
	l=lds[nod].size();
	for(i=0;i<l;i++){
		int x=lds[nod][i];
		if(v[x]==1){
		dfs1(x);
	}
	}
	sl.push_back(nod);
}
int main(){
	int i, m, j, x, y;
	ifstream f("ctc.in");
	ofstream g("ctc.out");
	f>>n>>m;
	while(m--){
		f>>x>>y;
		lda[x].push_back(y);
		lds[y].push_back(x);
	}
	for(i=1;i<=n;i++)if (v[i]==0){
		dfs(i);
	}
	for(i=k;i>=1;i--)if(v[c[i]]==1){
		sl.clear();
		dfs1(c[i]);
		sol.push_back(sl);
	}
	g<<sol.size()<<endl;
	int l=sol.size();
	for(i=0;i<l;i++)
	{
		int l1=sol[i].size();
		for(j=0;j<l1;j++){
		g<<sol[i][j]<<" ";
	}
	g<<endl;
	}
	return 0;
}