semafor2 - 100p

#include <bits/stdc++.h>

using namespace std;

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

int N, M, cnt;
vector<vector<int>> G, GT;
vector<int> viz, ctc, sz;
stack<int> S;

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

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

int main() {
    fin >> N >> M;
    G.resize(N << 1 | 1), GT.resize(N << 1 | 1);
    while(M--) {
        int a, b;
        bool c;
        fin >> a >> b >> c;
        if(c) {
            G[a].emplace_back(b + N);
            GT[b + N].emplace_back(a);
        }
        else {
            G[a + N].emplace_back(b);
            GT[b].emplace_back(a + N);
        }
    }
    viz.resize(N << 1 | 1);
    for(int i = 1; i <= (N << 1); ++i)
        if(!viz[i])
            dfs1(i);
    ctc.resize(N << 1 | 1), sz.resize(N << 1 | 1);
    while(!S.empty()) {
        int node = S.top();
        S.pop();
        if(viz[node] == 1) {
            ++cnt;
            dfs2(node);
        }
    }
    for(int i = 1; i <= N; ++i)
        if(sz[ctc[i]] > 1 || sz[ctc[i + N]] > 1)
            fout << '1';
        else
            fout << '0';
}