Cod sursa(job #1888099)

Utilizator jordan1998Jordan jordan1998 Data 21 februarie 2017 22:11:38
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define buffs 1048576
using namespace std;
FILE*f=freopen("dfs.in","r",stdin);
int n,pos=0,m,i,a,b,nrc=0;
bool viz[100002];
char buff[buffs];
std::vector<int>v[100002];
inline void read ( int &nr)
{
nr=0;
while(buff[pos]<'0'||buff[pos]>'9') if(++pos==buffs)fread(buff,1,buffs,stdin),pos=0;
while(buff[pos]>='0'&&buff[pos]<='9')
{
    nr=(nr<<1)+(nr<<3)+buff[pos]-48;
    if(++pos==buffs)fread(buff,1,buffs,stdin),pos=0;
}
}
inline void DFS(int x)
{
    int i,lg;
    viz[x]=1;
    lg=v[x].size();
    for(i=0;i<lg;i++)
        if(!viz[v[x][i]]) DFS(v[x][i]);
}
int main()
{fread(buff,1,buffs,stdin);
freopen("dfs.out","w",stdout);
    read(n);read(m);
for(i=1;i<=m;i++)
{
    read(a);read(b);
    v[a].push_back(b);
}
  for(i=1;i<=n;i++)
    if(!viz[i])
  {
      nrc++;
      DFS(i);
  }
  printf("%d",nrc);
}