Pagini recente » Cod sursa (job #2979209) | Cod sursa (job #3181596) | Cod sursa (job #762888) | Cod sursa (job #2587436) | Cod sursa (job #475580)
Cod sursa(job #475580)
// 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;
}