3-Coloring

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

void colorsdfs(vector<int>& g, vector<int>& colors, int s, int color) {
    if (colors[s] == -1) {
        colors[s] = color;
        colorsdfs(g, colors, g[s], (color + 1) % 3);
    }
}

void topologicalSortUtil(int v, vector<int>& adj,
                         vector<bool>& visited,
                         stack<int>& Stack) {
    visited[v] = true;

    int i = adj[v];
    if (!visited[i])
        topologicalSortUtil(i, adj, visited, Stack);

    Stack.push(v);
}

stack<int> topologicalSort(vector<int>& adj, int V) {
    stack<int> Stack;
    vector<bool> visited(V, false);
    for (int i = 0; i < V; i++) {
        if (!visited[i])
            topologicalSortUtil(i, adj, visited, Stack);
    }

    return Stack;
}

int main() {
    int n;
    cin >> n;
    vector<int> g(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        --x;
        g[i] = x;
    }

    stack<int> topo = topologicalSort(g, n);
    vector<int> colors(n, -1);
    int color = 0;
    while (!topo.empty()) {
        int x = topo.top();
        topo.pop();
        colors[x] = color;
        color = (color + 1) % 3;
    }

/*
    for (int i = 0; i < n; i++) {
        if (colors[g[i]] == -1) {
            colorsdfs(g, colors, i, 0);
        } else {
            colorsdfs(g, colors, i, 0);
        }
    }
*/

    for (int i = 0; i < n; i++) {
        cout << colors[i] + 1 << ' ';
    }
    cout << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER