Cod sursa(job #1951352)

Utilizator wilson182Alexandrina Panfil wilson182 Data 3 aprilie 2017 16:14:39
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<bits/stdc++.h>
using namespace std;
const int N=100020;
vector <int> lda[N], ldt[N], l, lc[N];
int v1[N], v2[N], nc;
void dfs1(int nod){
	v1[nod]=1;
	int x=lda[nod].size();
	for(int i=0;i<x;i++) if(!v1[lda[nod][i]]){
		dfs1(lda[nod][i]);
	}
	l.push_back(nod);
}
void dfs(int nod){
	int x=ldt[nod].size();
	v2[nod]=1;
	for(int i=0;i<x;i++) if(!v2[ldt[nod][i]])dfs(ldt[nod][i]);
	lc[nc].push_back(nod);
}
int main(){
    int n, m;
    ifstream f("ctc.in");
    ofstream g("ctc.out");
	f>>n>>m;
	int x, y;
	while(m--){
		f>>x>>y;
		lda[x].push_back(y);
		ldt[y].push_back(x);
	}
	for(int i=1;i<=n;i++)if(!v1[i]) dfs1(i);
	for(int i=l.size()-1; i>=0;i--) if(!v2[l[i]]){
		nc++;
		dfs(l[i]);
	}
	g<<nc<<endl;
	for(int i=1;i<=nc;i++){
		int x=lc[i].size();
		for(int j=0;j<x;j++) g<<lc[i][j]<<' ';
		g<<endl;
	}
}