Cod sursa(job #1505559)

Utilizator ilinoiuflaviusIlinoiu Flavius ilinoiuflavius Data 19 octombrie 2015 13:34:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#define nmax 100001
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int n,m,cc;
bool viz[nmax];

struct nod
{
    int nr;
    nod *p;
}v[nmax];

void read();
void solve();
void write();
void add(int,int);
void dfs(int);

int main()
{
    read();
    solve();
    write();
    return 0;
}
void read()
{
    f>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        add(a,b);
        add(b,a);
    }
}
void add(int a,int b)
{
    nod*q = new nod;
    q->nr = b;
    q->p = v[a].p;
    v[a].p = q;
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
        {
            cc++;
            dfs(i);
        }
    }
}
void dfs(int x)
{
    viz[x]=cc;
    for(nod *q = v[x].p ; q!=NULL; q=q->p)
    {
        if(!viz[q->nr])dfs(q->nr);
    }
}
void write()
{
    g<<cc;
}