Cod sursa(job #1813494)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 22 noiembrie 2016 23:27:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia7-grafuri Marime 0.74 kb
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define  MaxN 100005
using namespace std;
  
FILE *IN,*OUT;
int N,M,Comp=0,X,Y;
bool visited[MaxN];
vector <int> Graph[MaxN];
void DFS(int node)
{
    visited[node]=true;
    for(int i=0;i<Graph[node].size();i++)
    {
        if(!visited[Graph[node][i]])
            DFS(Graph[node][i]);
    }
}
int main()
{
    IN=fopen("dfs.in","r");
    OUT=fopen("dfs.out","w");
 
    fscanf(IN,"%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        fscanf(IN,"%d%d",&X,&Y);
        Graph[X].push_back(Y);
        Graph[Y].push_back(X);
    }
    for(int i=1;i<=N;i++)
        if(!visited[i])DFS(i),Comp++;
    fprintf(OUT,"%d",Comp);
 
    return 0;
}