Cod sursa(job #2083720)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 8 decembrie 2017 00:53:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

inline void debugMode() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    #ifndef ONLINE_JUDGE
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    #endif // ONLINE_JUDGE
}
inline void PrintYes() { cout << "Yes"; }
inline void PrintNo() { cout << "No"; }

const double eps = 1e-7;
const int Nmax = 1e5 + 5;

vector < int > G[Nmax];
bool viz[Nmax];
int colors[Nmax];
int color;

void DFS(int nod, int color)
{
    viz[nod] = true;
    colors[nod] = color;

    for(auto it: G[nod])
        if(viz[it] == false)
            DFS(it, color);
}

int main()
{
	debugMode();

    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int x , y;
        cin >> x >> y;

        G[x - 1].push_back(y - 1);
        G[y - 1].push_back(x - 1);
    }

    for(int i = 0; i < n; ++i)
        if(viz[i] == false)
            DFS(i, ++color);

    int ans = -1;
    for(int i = 0; i < n; ++i)
        if(colors[i] > ans)
            ans = colors[i];

    cout << ans;
	return 0;
}