Cod sursa(job #2221269)

Utilizator danielsociuSociu Daniel danielsociu Data 13 iulie 2018 15:39:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
std::ifstream cin("dfs.in");
std::ofstream cout("dfs.out");
#define maxn 100010
typedef struct nod{
    nod* next;
    int where;
}*GRAF;
int viz[maxn]={0},n,m;
GRAF g[maxn];

void add(GRAF &g,int val){
    GRAF p=new nod;
    p->where=val;
    p->next=g;
    g=p;
}

void dfs(int x){
    viz[x]=1;
    for(GRAF xd=g[x];xd;xd=xd->next)
        if(!viz[xd->where])
            dfs(xd->where);
}

int main()
{
    int x,y,ans=0;
    cin>>n>>m;
    GRAF *it;
    while(cin>>x>>y){
        add(g[x],y);
        add(g[y],x);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i]){
            dfs(i);
            ans++;
        }
    cout<<ans;
    return 0;
}