Cod sursa(job #1808126)

Utilizator sotoc1999Sotoc George sotoc1999 Data 17 noiembrie 2016 13:07:05
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m;
//bool a[102][102];
int x,y;
bool viz[100004];
int nr;
struct nod{
    int val;
    struct nod *urm;
}*L[100003],*actual;
/*void dfs(int k)
{
    g<<k<<" ";
    int i;
    for(i=1;i<=n;i++)
    {
        if(a[k][i]==true&&viz[i]==false)
        {
            viz[i]=true;
            dfs(i);
        }
    }
}*/
void dfs_recursiv(int k)
{
    struct nod *act;
    viz[k]=true;
    act=L[k];
    while(act!=NULL)
    {
        if(viz[act->val]==false)
            dfs_recursiv(act->val);
        act=act->urm;
    }
}
int componente_conexe()
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==false)
        {
            nr++;
            dfs_recursiv(i);
        }
    }
    return nr;
}
int main()
{
    f>>n>>m;
    int i;
    /*for(i=1;i<=m;i++)
    {
        f>>val>>val1;
        a[val][val1]=1;
        a[val1][val]=1;
    }
    viz[x]=1;
    dfs(x); */
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        actual=new nod;
        actual->val=x;
        actual->urm=L[y];
        L[y]=actual;

        actual=new nod;
        actual->val=y;
        actual->urm=L[x];
        L[x]=actual;
    }
    int val=componente_conexe();
    g<<val;
    return 0;
}