Cod sursa(job #3277585)

Utilizator marco_mihocMihoc Marco marco_mihoc Data 16 februarie 2025 19:05:08
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
struct nod
{
    int vf;
    nod *urm;
}*v[100001];
int n,m,viz[101],k;
void add(nod *&prim,int x)
{
    nod *q=new nod;
    q->vf=x;
    q->urm=prim;
    prim=q;
}
void read()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(v[x],y);
        add(v[y],x);
    }
}
void dfs(int p)
{
    viz[p]=k;
    for(nod *q=v[p];q;q=q->urm)
        if(viz[q->vf]==0)
            dfs(q->vf);
}
int main()
{
    read();
    for(int i=1;i<n;i++)
        if(viz[i]==0)
        {
            k++;
            dfs(i);
        }
    cout<<k;
    return 0;
}