Cod sursa(job #475580)

Utilizator robigiirimias robert robigi Data 7 august 2010 16:08:39
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
// Componente tare conexe.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("ctc.in", "r");
FILE *g=fopen("ctc.out", "w");

typedef struct nod
{
	int x;
	struct nod *adr;
};

nod *l[100001];
nod *ll[100001];

int n, m;
int postordine[100001];
int viz[100001];
int nr, nrc;


void add(int x, int y)
{
	nod *p=new nod;
	p->x=y;
	p->adr=l[x];
	l[x]=p;
}

void add2(int x, int y)
{
	nod *p=new nod;
	p->x=y;
	p->adr=ll[x];
	ll[x]=p;
}

void read()
{
	fscanf(f, "%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		int x, y;
		fscanf(f, "%d%d", &x, &y);
		add(x, y);
		add2(y, x);
	}
}


void dfs(int x)
{
	viz[x]=1;
	nod *p=l[x];
	while (p!=NULL)
	{
		if (!viz[p->x])
			dfs(p->x);
		p=p->adr;
	}
	postordine[++nr]=x;
}


void dfst(int x)
{
	viz[x]=0;
	nod *p=ll[x];
	while (p!=NULL)
	{
		if (viz[p->x])
			dfst(p->x);
		p=p->adr;
	}
}


void program()
{
	dfs(1);
	for (int i=n; i>0; --i)
	{
		if (viz[postordine[i]])
		{
			dfst(postordine[i]);
			++nrc;
		}
	}
	fprintf(g, "%d\n", nrc);
}



int main()
{
	read();
	program();

	fclose(f);
	fclose(g);
	return 0;
}