Cod sursa(job #1821731)

Utilizator PinkiePie1189Preoteasa Mircea-Costin PinkiePie1189 Data 3 decembrie 2016 15:39:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<stdio.h>
#include<vector>
#define MAXN 100001
FILE*fin,*fout;
inline void Adauga(int x,int lista);
void dfs(int nod);
std::vector<int> Lista[MAXN];
bool seen[MAXN];
int k;
int main()
{
    fin=fopen("dfs.in","r");
    fout=fopen("dfs.out","w");
    int N,M;
    fscanf(fin,"%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        int x,y;
        fscanf(fin,"%d%d",&x,&y);
        Adauga(x,y);
        Adauga(y,x);
    }
    int ans=0;
    for(int i=1;i<=N;i++)
    {
        if(!seen[i])
        {
            ans++;
            seen[i]=1;
            dfs(i);
        }
    }
    fprintf(fout,"%d",ans);
    fclose(fin);
    fclose(fout);
    return 0;
}
inline void Adauga(int x,int lista)
{
    Lista[lista].push_back(x);
}
void dfs(int nod)
{
    for(int i=0;i<Lista[nod].size();i++)
    {
        if(!seen[Lista[nod][i]])
        {
            seen[Lista[nod][i]]=1;
            dfs(Lista[nod][i]);
        }
    }
}