DPRTMNTSEASY - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Authors: Abhiram M, Hriday
Testers: Jeevan Jyot Singh, Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

2400

PREREQUISITES:

Observation

PROBLEM:

You are given a graph G representing connections in a company. You know that G has the following structure:

  • For some integer M, there are M departments. Each department has a manager.
  • All the managers are connected to each other
  • All the members of a department are connected to each other
  • No other connections exist

Find the number of departments, the managers of the departments, and which employees belong to which department.

In the easy version, you further know that each department has a minimum of two people in it.

EXPLANATION:

Easy version

Look at the vertex with the smallest degree, say u. If M \gt 1, u is guaranteed to not be a manager.

Why?

Consider the department u belongs to. Suppose it has k people.
The non-managers of this department will all have the same degree, i.e k-1.
Note that if there are M departments, the manager will have degree k-1+M-1, which is strictly more than k-1 when M\gt1.

Since every department has two people in it, there definitely exists a non-manager employee. So, u is definitely not a manager.

Note that when M = 1, it doesn’t matter who is chosen as the manager. So, for our purposes we can always assume that u is not a manager (even though we don’t know M yet).

Now, the above discussion tells us this:

  • Suppose u has degree k. Then, k-1 of its neighbors will also have degree k, being non-manager employees in the same department.
  • Exactly one neighbor of u will have a degree higher than k. Let this be v. v is the manager of u's department.
  • Once we know v, we know all the other managers: they are all the neighbors of v who are not neighbors of u. This also tells us the number of departments.
  • Knowing all the managers allows us to form the departments in similar fashion: if w is a manager, the members of that department are then all the neighbors of w who are not managers.

This gives us all the information we need: we know the number of departments, the managers of each department, and the members of each department.

Hard version

The only difference here is that there might be some department with only one person. In particular, when looking at the vertex of lowest degree, they can possibly be a manager this time.

However, note that there are only two cases possible:

  • First, if u is not a manager, the exact same solution as the easy version applies.
  • Second, if u is a manager, then we know all the managers: they are simply all the neighbors of u. Just as above, knowing all the managers allows to reconstruct all the departments.

Try both cases!

Assume u is a manager, and try to reconstruct a solution. If you succeed, great! Print the solution you obtained and continue on.
If you fail, then the only possibility is that u is not a manager. Now apply the solution to the easy version and you are done.

Maximum degree

There is an alternate approach that looks at the maximum degree instead of the minimum degree, although it ends up being quite similar in the end.

Note that the vertex with maximum degree is always going to be a manager. So, some of its neighbors are all the other managers, and the remaining are the members of its department.

Notice that these two sets each form a clique, and are disjoint from each other. This allows us to compute these disjoint sets quite easily. Then, check for each one of them whether there is a valid solution with that set as the managers.

TIME COMPLEXITY

\mathcal{O}(N^2) per test case.

CODE:

Setter's code (C++, easy version)
/**
 * the_hyp0cr1t3
 * 30.08.2022 01:23:14
**/
#ifdef W
    #include <k_II.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
#endif

int main() {
#if __cplusplus > 201703L
    namespace R = ranges;
#endif
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int tests; cin >> tests;
    while(tests--) [&] {
        int i, N, K;
        cin >> N >> K;

        if(K == N * (N - 1) / 2) {
            // There is just one department.
            while(K--) cin >> i >> i;

            cout << 1 << '\n';
            for(i = 0; i < N; i++)
                cout << 1 << " \n"[i + 1 == N];
            cout << 1 << '\n';

        } else {

            vector<int> deg(N);
            vector<vector<int>> adj(N);
            while(K--) {
                int u, v; cin >> u >> v;
                ++deg[--u];
                ++deg[--v];
                adj[u].push_back(v);
                adj[v].push_back(u);
            }

            // Find the employee with minimum degree (guaranteed not to be a leader).
            int min_v = min_element(deg.begin(), deg.end()) - deg.begin();

            int leader;
            vector<bool> mark(N, false);
            mark[min_v] = true;
            for(int u: adj[min_v]) {
                if(deg[u] == deg[min_v]) {
                    mark[u] = true;
                } else {
                    // The department head is the sole vertex connected
                    // to [min_v] with a greater degree.
                    leader = u;
                }
            }

            // Having marked all the vertices in the department of [min_v],
            // the unmarked vertices connected to [leader] are all the leaders of all the other departments.
            // Getting their department sizes is easy and can be done as follows.
            int M = 0;
            vector<int> col(N, -1), leaders;
            adj[leader].push_back(leader);
            for(int u: adj[leader]) {
                if(!mark[u]) {
                    col[u] = M++;
                    leaders.push_back(u);
                }
            }

            for(int v: leaders)
                for(int u: adj[v])
                    if(col[u] == -1) col[u] = col[v];

            cout << M << '\n';
            for(i = 0; i < N; i++)
                cout << col[i] + 1 << " \n"[i + 1 == N];
            for(i = 0; i < M; i++)
                cout << leaders[i] + 1 << " \n"[i + 1 == M];
        }

    }();

} // ~W
Setter's code (C++, hard version)
/**
 * the_hyp0cr1t3
 * 30.08.2022 01:23:14
**/
#ifdef W
    #include <k_II.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
#endif

int main() {
#if __cplusplus > 201703L
    namespace R = ranges;
#endif
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int tests; cin >> tests;
    while(tests--) [&] {
        int i, N, K;
        cin >> N >> K;

        vector<int> deg(N);
        vector<vector<int>> adj(N);
        while(K--) {
            int u, v; cin >> u >> v;
            ++deg[--u]; ++deg[--v];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        int min_v = min_element(deg.begin(), deg.end()) - deg.begin();

        vector<int> leaders, col(N, -1);
        vector<bool> mark(N, false);
        mark[min_v] = true;
        for(int u: adj[min_v]) {
            if(deg[u] == deg[min_v])
                mark[u] = true;
            else
                leaders.push_back(u);
        }

        if(leaders.size() != 1) {
            leaders = adj[min_v];
            leaders.push_back(min_v);
        } else {
            for(int u: adj[leaders[0]])
                if(!mark[u]) leaders.push_back(u);
        }

        int M = 0;
        for(int l: leaders) col[l] = M++;

        for(int l: leaders)
            for(int u: adj[l])
                if(col[u] == -1) col[u] = col[l];

        cout << M << '\n';
        for(i = 0; i < N; i++)
            cout << col[i] + 1 << " \n"[i + 1 == N];
        for(i = 0; i < M; i++)
            cout << leaders[i] + 1 << " \n"[i + 1 == M];
    }();

} // ~W
Tester's code (C++, hard version)
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

int sumN = 0;

void solve()
{
    int n = readIntLn(2, 1000);
    int k = readIntLn(1, n * (n - 1) / 2);
    sumN += n;
    vector<vector<int>> g(n + 1);
    vector<int> deg(n + 1);
    set<pii> edges;
    for(int i = 0; i < k; i++)
    {
        int u = readIntSp(1, n);
        int v = readIntLn(1, n);
        assert(u != v);
        edges.insert({min(u, v), max(u, v)});
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++, deg[v]++;
    }
    assert(sz(edges) == k);
    int mn = min_element(deg.begin() + 1, deg.end()) - deg.begin();
    vector<int> neighmn;
    for(int x: g[mn])
        neighmn.push_back(deg[x]);
    int cnt = count(neighmn.begin(), neighmn.end(), deg[mn]);
    if(cnt == sz(neighmn) - 1)
    {
        int leader = -1;
        set<int> curcomp;
        for(int x: g[mn])
            if(deg[x] > deg[mn])
                leader = x;
            else
                curcomp.insert(x);
        curcomp.insert(mn);
        set<int> leaders{leader};
        for(int x: g[leader])
        {
            if(!curcomp.count(x))
                leaders.insert(x);
        }
        int cur = 1;
        vector<int> col(n + 1);
        for(int L: leaders)
        {
            col[L] = cur++;
            for(int x: g[L])
                if(!leaders.count(x))
                    col[x] = col[L];
        }
        cout << sz(leaders) << endl;
        for(int i = 1; i <= n; i++)
            cout << col[i] << " ";
        cout << endl;
        for(int x: leaders)
            cout << x << " ";
        cout << endl;
    }
    else
    {
        int leader = mn;
        set<int> leaders{leader};
        for(int x: g[leader])
        {
            leaders.insert(x);
        }
        int cur = 1;
        vector<int> col(n + 1);
        for(int L: leaders)
        {
            col[L] = cur++;
            for(int x: g[L])
                if(!leaders.count(x))
                    col[x] = col[L];
        }
        cout << sz(leaders) << endl;
        for(int i = 1; i <= n; i++)
            cout << col[i] << " ";
        cout << endl;
        for(int x: leaders)
            cout << x << " ";
        cout << endl;
    }
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 1000);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    readEOF();
    assert(sumN <= 3000);
    return 0;
}
Editorialist's code (C++, hard version)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	int t; cin >> t;
	while (t--) {
		int n, k; cin >> n >> k;
		vector adj(n+1, vector(n+1, 0));
		for (int i = 0; i < k; ++i) {
			int u, v; cin >> u >> v;
			adj[u][v] = adj[v][u] = 1;
		}
		int ch = 0, mx = 0;
		for (int i = 1; i <= n; ++i) {
			int deg = count(begin(adj[i]), end(adj[i]), 1);
			if (deg > mx) {
				mx = deg;
				ch = i;
			}
		}
		vector<int> cand1, cand2;
		for (int i = 1; i <= n; ++i) {
			if (!adj[ch][i]) continue;
			if (cand1.empty()) cand1.push_back(i);
			else {
				if (adj[cand1[0]][i]) cand1.push_back(i);
				else cand2.push_back(i);
			}
		}
		cand1.push_back(ch); cand2.push_back(ch);
		auto check = [&] (auto cand) {
			vector<int> mark(n+1);
			int idx = 1;
			for (int x : cand) mark[x] = idx++;
			for (int i = 1; i <= n; ++i) {
				if (mark[i]) continue;
				int found = 0;
				for (int x : cand) {
					if (adj[i][x]) {
						mark[i] = mark[x];
						++found;
					}
				}
				if (found != 1) return false;
			}
			cout << size(cand) << '\n';
			for (int i = 1; i <= n; ++i) cout << mark[i] << ' ';
			cout << '\n';
			for (int x : cand) cout << x << ' ';
			cout << '\n';
			return true;
		};
		assert(check(cand1) || check(cand2));
	}
}
2 Likes

For the Easy Version, I am using the Articulation Vertex Algorithm to find the managers in the graph, since the managers are those nodes which if cut out from the graph increases the connected components in the graph and thus, they can be treated as articulation vertices and once we know the managers the employees in their departments can easily be found. But This technique is not giving me correct answer for all the test cases, I appreciate if anyone can help me find failure cases for this algorithm?

Yeah in the starting i also gone through the same approach but i think you missed out some statment which states that all the head of each department are connected to each other it means that all the head of the department themselves formed an SSC so you will not get any articulation vertex at all the only vertex you get is that one which department has only 2 employee