Admitere P3 iasi 2024

#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int mxN = 1e3;
int adj[mxN][mxN];
int col[mxN], usedCol[mxN], visited[mxN];
int n , m , k;
void DFS(int node)
{
    visited[node] = true;
    // Determinam culoarea :
    int culoare = -1;
    for(int i = 0;i<n;i++)
        if(adj[node][i])
            usedCol[col[i]] = true;
    for(int i = 1;i <= n - k;i++)
        if(usedCol[i] == false)
        {
           culoare = i;
           break;
        }
    col[node] = culoare;
    // Resetam tabloul de culori folosite.
    for(int i = 1;i<= n - k;i++)
        usedCol[i] = false;
    // Facem DFS in vecinii nevizitati
    for(int i = 0;i<n;i++)
        if(adj[node][i] && !visited[i])
            DFS(i);

}
int main()
{
    cin >> n >> m >> k;
    for(int i = 1;i<=m;i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a][b] = adj[b][a] = 1;
    }
    // Obtinem complementul grafului
    for(int i = 0;i<n;i++)
        for(int j = 0;j<n;j++)
            if(i!=j)
                adj[i][j] = 1 - adj[i][j];
    for(int i = 0;i<n;i++)
        if(!visited[i])
            DFS(i);
    for(int i = 1;i<=n-k;i++)
    {
        int cnt = 0;
        for(int it = 0;it<n;it++)
            if(col[it] == i)
                cnt++, cout << it << ' ';
        if(cnt > 0) cout << '\n';
    }
    return 0;
}
/*
In input se presupune indexarea nodurilor de la 0.
Daca nu este asa, se poate face a--, b-- cand se citesc muchiile.
6 6 2
0 1
0 2
1 2
3 4
3 5
4 5
*/