Cod sursa(job #921866)

Utilizator alexandrul_21Niculescu Mihai alexandrul_21 Data 21 martie 2013 18:43:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;
#define MAX_N 100000
struct nod
{
    int nr;
    nod *next;
}*First[MAX_N+5];
int N,M;
int Visited[MAX_N+5];
void Insert(int x,int y)
{
    nod *q=new nod;
    q->nr=y;
    q->next=First[x];
    First[x]=q;
}
void Read()
{
    ifstream fin("dfs.in");
    fin>>N>>M;
    int i,x,y;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        Insert(x,y);
        Insert(y,x);
    }
    fin.close();
}
void DF(int k)
{
    Visited[k]=1;
    nod *q;
    for(q=First[k];q;q=q->next)
    {
        if(Visited[q->nr]==0)
            DF(q->nr);
    }
}
int Resolve()
{
    int i,s=0;
    for(i=1;i<=N;i++)
    {
        if(Visited[i]==0)
        {
            DF(i);
            s++;
        }
    }
    return s;
}
int main()
{
    Read();
    ofstream fout("dfs.out");
    fout<<Resolve();
    fout.close();
    return 0;
}