Pagini recente » Cod sursa (job #129268) | Cod sursa (job #440764) | Cod sursa (job #1183409) | Cod sursa (job #793317) | Cod sursa (job #1113634)
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int Nmax=100000;
const int Mmax=1000000;
int n,m,viz[Nmax],d;
struct lista
{ int v;
lista *urm;
};
lista *cap[Nmax],*nou;
int vecin(int ns,int i)
{ nou=cap[ns];
while(nou)
{ if(viz[i]==0&&i==nou->v)
return 1;
nou=nou->urm;
}
return 0;
}
void dfs(int ns)
{ int i;
viz[ns]=1;
for(i=1;i<=n;i++)
{ if(vecin(ns,i)==1)
dfs(i);
}
}
int main()
{
int i,a,b;
in>>n>>m;
for(i=1;i<=m;i++)
{ in>>a>>b;
nou=new lista;
nou->v=b;
nou->urm=cap[a];
cap[a]=nou;
}
for(i=1;i<=n;i++)
{ if(viz[i]==0)
{ d++;
dfs(i);
}
}
out<<d;
return 0;
}