Pagini recente » Cod sursa (job #1061435) | Monitorul de evaluare | Cod sursa (job #1912049) | Cod sursa (job #2002505) | Cod sursa (job #1113654)
#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,j,p;
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 j)
{ int i;
viz[ns]=1;
for(i=j;i<=n;i++)
{ if(viz[i]==0)
if(vecin(ns,i)==1)
dfs(i,j);
}
}
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;
nou=new lista;
nou->v=a;
nou->urm=cap[b];
cap[b]=nou;
}
for(i=1;i<=n;i++)
{ if(viz[i]==0)
{ d++;
p=i;
dfs(i,p);
}
}
out<<d;
return 0;
}