Cod sursa(job #2075265)

Utilizator BourucLiviuBouruc Petru Liviu BourucLiviu Data 25 noiembrie 2017 12:25:06
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <vector>

using namespace std;

int n, d[1005];
bool viz[1005];
vector <int> G[1005], sp;
vector <pair <int, int> > comp, compsp;

int nrM, nrN;
void DFS(int x)
{
    viz[x] = 1;
    nrN++; nrM += d[x];
    for(int i = 0; i < G[x].size(); ++i)
        if(!viz[G[x][i]) DFS(G[x][i]);
}

int main()
{
    int m, k;
    cin >> n >> m >> k;
    for(int i = 1, x; i <= k; ++i)
    {
        cin >> x;
        sp.push_back(x);
    }
    for(int i = 1, x, y; i <= m; ++i)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
        d[x]++; d[y]++;
    }

    int Max = -1, maxComp;
    for(int i = 0; i < sp.size(); ++i)
    {
        nrN = 0; nrM = 0;
        DFS(sp[i]);
        compsp.push_back(make_pair(nrN, nrM/2));
        if(nrN > Max)
        {
            Max = nrN;
            maxComp = sp[i];
        }
    }
    for(int i = 1; i <= n; ++i)
        if(!viz[i])
        {
            nrN = 0; nrM = 0;
            DFS(i);
            comp.push_back(make_pair(nrN, nrM/2));
        }

    return 0;
}