Cod sursa(job #2348819)

Utilizator Horea_Mihai_SilaghiHorea Mihai Silaghi Horea_Mihai_Silaghi Data 20 februarie 2019 00:19:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>

using namespace std;

int n,m,viz[100005],cnt=0;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
typedef struct nod
{
    int x;
    nod *a;
}*pnod;

pnod v[100005];
void add(pnod &dest, int val)
{
    pnod p=new nod;
    p -> x=val;
    p -> a=dest;
    dest = p;
}
void citire()
{
    int x,y;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        add(v[x],y);
        add(v[y],x);
    }
}
void dfs(int k)
{
    pnod p;
    viz[k]=1;
    for( p = v[k] ; p != NULL ; p = p -> a)
        if(viz[p -> x]==0)
            dfs(p -> x);
}
int main()
{
    citire();
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            cnt++;
            dfs(i);
        }
    }
    cout<<cnt;
    return 0;
}