Cod sursa(job #1552614)

Utilizator GrandmasterSoucup Bogdan Grandmaster Data 18 decembrie 2015 12:34:42
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
#include <map>
#include <iomanip>
#include <time.h>
#include <stdio.h>
//#include <iostream>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int vec[1000001];
int n, m, a, b, x[1001][1001];
void DFS(int x[][1001], int n, int nodstart)
{
    int head = 0, tail = 1;
    vec[0] = nodstart;
    while(head != tail){
        for(int i = 0; i < n; i++)
        {
            if(x[vec[head]][i] == 1){
                x[vec[head]][i] = 2;
                x[i][vec[head]] = 2;
                vec[tail++] = i;
            }
        }
        head++;
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        x[a - 1][b - 1] = 1;
        x[b - 1][a - 1] = 1;
    }
    int k = 0, ok = 0;
    for(int i = 0; i < n; i++){
        ok = 0;
        for(int j = 0; j < n; j++){
            if(x[i][j] == 1)
            {
                k++;
                DFS(x, n, i);
                ok = 1;
            }
            if(x[i][j] == 2)
                ok = 1;
        }
        if(ok == 0)
        k++;
    }
    cout << k;
    return 0;
}