Cod sursa(job #630240)

Utilizator the_snyper06FMI - ALexandru Mihai the_snyper06 Data 4 noiembrie 2011 23:37:22
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<cstdio>
#include<vector>

using namespace std;
int n, m, st[100001], pred[100001];
vector <int> LGraf[100001], LGrafInv[100001];
bool viz[100001];

void BF(int k)
{
	int pr, ul;
	unsigned int i;
	
	pr = ul = 0;
	st[ul] = k;
	
	while(pr <= ul)	{
		k = st[pr++];
		for(i = 0; i < LGrafInv[k].size(); i++)
			if(!viz[LGrafInv[k][i]]) {
				st[++ul] = LGrafInv[k][i];
				viz[LGrafInv[k][i]] = true;
				pred[LGrafInv[k][i]] = k;
			}
	}
}

int main() {
	int i, x, y, nr;
	
	freopen("ctc.in", "r", stdin), freopen("ctc.out", "w", stdout);
	scanf("%d %d", &n, &m);
	
	for(i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		LGraf[x].push_back(y);
		LGrafInv[y].push_back(x);
	}
	
	nr = 0;
	for(i = 1; i <= n; i++)
		if(!viz[i]) {
			nr++;
			BF(i);
		}
	
	printf("%d\n", nr);
		
	return 0;
}