Cod sursa(job #1891031)

Utilizator wilson182Alexandrina Panfil wilson182 Data 23 februarie 2017 18:15:37
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 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;
	for(i=0;i<lda[nod].size();i++) if(!v[lda[nod][i]]){
		dfs(lda[nod][i]);
	}
	c[++k]=nod;
}
void dfs1(int nod){
	int i;
	v[nod]=2;
	for(i=0;i<lds[nod].size();i++)if(v[lds[nod][i]]==1){
		dfs1(lds[nod][i]);
	}
	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;
	for(i=0;i<sol.size();i++)
	{
		for(j=0;j<sol[i].size();j++){
		g<<sol[i][j]<<" ";
	}
	g<<endl;
	}
	return 0;
}