Cod sursa(job #1527580)

Utilizator asdasd12asdasd asdasd12 Data 18 noiembrie 2015 13:07:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
#include<iostream>
int v[100001];
using namespace std;
int n,m,i,u,o;
struct node
{
int vecin;
node *next;
}*G[100001];

void isrt(int l, int e)
{
node *p=new node;
p->next=G[l];
p->vecin=e;
G[l]=p;
}

void dfs(int l)
{
node *q=G[l];
    while(q)
    {
     if(v[q->vecin]!=1)
          {
           v[q->vecin]=1;
           dfs(q->vecin);
          }
    q=q->next;
    }
}

int main(){
ifstream f("dfs.in");
ofstream g("dfs.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
 f>>u>>o;
 isrt(u,o);
 isrt(o,u);
}
int nr=0;
for(i=1;i<=n;i++)
{
 if(v[i]!=1)
 {
    v[i]=1;
    nr++;
    dfs(i);
 }
}
g<<nr;

return 0;
}