Cod sursa(job #1890116)

Utilizator wilson182Alexandrina Panfil wilson182 Data 23 februarie 2017 08:32:13
Problema Componente tare conexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 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 nod{
	int val;
	nod* next;
	nod(){
		next=NULL;
	}
};
nod* L=NULL;
struct p{
	int v, ind;
} a[N];
	ifstream f("ctc.in");
	ofstream g("ctc.out");
void add(nod* &a, int val){
	if(a==NULL){
		a = new nod;
		a->val=val;
		return;
	}
	nod* b=new nod;
	b->val=val;
	b->next=a;
	a=b;
}
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;
		add(L, 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]){
//		col++;
		dfs1(i);
	}
	
	for(i=1;i<=n;i++)v[i]=0;
	nod* r=L;
	for(; r;r=r->next){
		
		if(!v[r->val]){
			col++;
			dfs(r->val);
		}
	}
	g<<col;
	return 0;
}