Cod sursa(job #2486163)

Utilizator ioncristescu7Ion Cristescu Marian ioncristescu7 Data 2 noiembrie 2019 13:21:21
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>

using namespace std;
struct node {
int value;
int next;
}memory[100002];
int start[100000];
int cnt=0;
bool marked[100001];
ifstream cin("dfs.in");
ofstream cout("dfs.out");
void kill(int i) {
    if(i==0)
        return;
    int cell=start[i];
    start[i]=0;
    marked[i]=1;
    while(cell!=-1) {
        kill(memory[cell].value);
        cell=memory[cell].next;
    }
    return;
}
int main()
{
    int n,m,x,y;
    cin >> n >> m;
    memory[0].value=0;
    memory[0].next=-1;
    for(int i=1; i<=m*2; i+=2)
    {
        cin >> x >> y;
        memory[i].value=x;
        memory[i].next=start[y];
        start[y]=i;
        memory[i+1].value=y;
        memory[i+1].next=start[x];
        start[x]=i+1;
    }
    int cnt=0;
    for(int i=1; i<=n; i++) {
        if(marked[i]==0) {
            kill(i);
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}