Cod sursa(job #1890093)

Utilizator wilson182Alexandrina Panfil wilson182 Data 23 februarie 2017 07:57:26
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<bits/stdc++.h>
#define N 100020
using namespace std;
vector <int> lda[N], lda1[N];
int t, v[N], c[N], col=0, b=0;
struct p{
	int v, ind;
} a[N];
	ifstream f("ctc.in");
	ofstream g("ctc.out");
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]);
	}
	++t;
	a[nod].v=t;
	a[nod].ind=nod;
}
void dfs1(int nod){
	v[nod]=1;
	if(b)g<<nod<<" ";
	int i;
	for(i=0;i<lda1[nod].size();i++)if(!v[lda1[nod][i]]){
		dfs1(lda1[nod][i]);
	}
	c[nod]=col;
}
int cmp(p a, p b){
	return(a.v>b.v);
}
int main(){
	int i, n, m, j, x, y;
	f>>n>>m;
	for(i=1;i<=m;i++){
		f>>x>>y;
		lda[x].push_back(y);
		lda1[y].push_back(x);
	}
	for(i=1;i<=n;i++)if(v[i]==0)dfs(i);
	sort(a+1, a+n+1, cmp);
	for(i=1;i<=n;i++)v[i]=0;
	for(i=1;i<=n;i++)if(!v[i]){
		col++;
		dfs1(i);
	}
	g<<col<<endl;
	b=1;
	for(i=1;i<=n;i++)v[i]=0;
	for(i=1;i<=n;i++)if(!v[i]){
		dfs1(i);
		g<<endl;
	}
	return 0;
}