semafor2 - 51p

#include <bits/stdc++.h>

using namespace std;

ifstream fin("semafor2.in");
ofstream fout("semafor2.out");

int N, M, cnt, nr;
vector<vector<pair<int,bool>>> G;
vector<vector<int>> GT, vis;
vector<int> viz, ctc;
stack<int> S;

void dfs1(int node) {
    viz[node] = 1;
    for(auto next : G[node])
        if(!viz[next.first])
            dfs1(next.first);
    S.emplace(node);
}

void dfs2(int node) {
    viz[node] = 2;
    ctc[node] = cnt;
    for(int next : GT[node])
        if(viz[next] == 1)
            dfs2(next);
}

bool dfs(int node, bool colour, int firstN, bool firstC) {
    vis[node][colour] = nr;
    for(auto next : G[node])
        if(ctc[next.first] == ctc[firstN] && next.second != colour && vis[next.first][next.second] != nr) {
            if(next.first == firstN && next.second != firstC)
                return true;
            if(dfs(next.first, next.second, firstN, firstC))
                return true;
        }
    return false;
}

int main() {
    fin >> N >> M;
    G.resize(N + 1);
    GT.resize(N + 1);
    while(M--) {
        int a, b;
        bool c;
        fin >> a >> b >> c;
        G[a].emplace_back(b, c);
        GT[b].emplace_back(a);
    }
    viz.resize(N + 1);
    for(int i = 1; i <= N; ++i)
        if(!viz[i])
            dfs1(i);
    ctc.resize(N + 1);
    while(!S.empty()) {
        int node = S.top();
        S.pop();
        if(viz[node] == 1) {
            ++cnt;
            dfs2(node);
        }
    }
    vis.resize(N + 1, vector<int>(2));
    for(int i = 1; i <= N; ++i) {
        bool ans = false;
        for(auto vec : G[i])
            if(ctc[vec.first] == ctc[i]) {
                ++nr;
                ans |= dfs(vec.first, vec.second, i, vec.second);
                if(ans)
                    break;
            }
        fout << ans;
    }
}