Cod sursa(job #2562156)

Utilizator s.gabi7Dumitrescu Daniel s.gabi7 Data 29 februarie 2020 12:32:10
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
using namespace std;

struct nod {
    int inf;
    nod *urm;
} *v[1000001];

void add (nod *&p, int x) {
    nod *e=new nod;
    e->inf=x;
    e->urm=p;
    p=e;
}

int vizitat[1000001], n, nr;

void DFS (int x) {
    nr++;
    for (nod *p=v[x]; p; p=p->urm)
        if (vizitat[p->inf]==0) {
            vizitat[p->inf]=1;
            DFS(p->inf);
        }

}

int main () {
    ifstream fin ("prieteni.in");
    ofstream fout ("prieteni.out");
    int m, c, x, y, j;
    fin >> n >> m;
    for (int i=1; i<=m; i++) {
        fin >> c;
        if (c==1) {
            fin >> x >> y;
            add(v[x], y);
            add(v[y], x);
        }
        else {
            fin >> x;
            nr=0;
            vizitat[x]=1;
            DFS(x);
            for (j=1; j<=n; j++)
                vizitat[j]=0;
            fout << nr << '\n';
        }
    }
    return 0;
}