SGU 219 Synchrograph 6/10

想了一想，一個有>0值的環，或一個沒有入度的都可以不斷不斷的燃燒

環是可以循環燃燒，沒有入度的則可以無限燃燒

唯一會燒不起來的好像就是全部都是0的環所以就用0邊做出新的圖，用SCC判斷一下誰不能燒

而且如果有一個人的上游是無法亂燒的，那他就也不能亂燒（也就是所謂的alive）所以要再DFS一下，他的下游是誰

我想到一個比較好的解釋方式：
1. 對零的邊的SCC縮點，縮起來的那個點代表他無法燃燒
2. 因為他沒辦法燃燒，所以他下游的點也都不能燃燒
3. 但假設你把1,2,所說的點去除掉之後，剩下的點再做縮點，（因為環可以不斷的循環，所以可以視為是一個點）
4. 最後變成了DAG，一定存在一個無入度點，他可以無限燃燒，所以剩下的那些點，都是alive的。

//By momo
#include
#include
#include
#define N 1010
#define PB push_back
#define SZ(x) ((int)(x).size())
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

int n, m, hit[N], cnt, vst[N];
vector<int> G[N], rG[N], tG[N], scc[N];
void dfs(int p){
    vst[p] = 1;
    FOR(it, G[p])
        if(!vst[*it]) dfs(*it);
    hit[cnt++] = p;
}
void rdfs(int p){
    vst[p] = 1;
    FOR(it, rG[p])
        if(!vst[*it]) rdfs(*it);
    scc[cnt].PB(p);
}
void kosaraju(){
    cnt = 0; fill(vst, vst + n, 0);
    for(int i = 0; i < n; i++)
        if(!vst[i]) dfs(i);
    cnt = 0; fill(vst, vst + n, 0);
    for(int i = n-1; i >= 0; i--)
        if(!vst[hit[i]]) rdfs(hit[i]), cnt++;
}

int dead[N];
void ddfs(int p){
    vst[p] = 1;
    FOR(it, tG[p])
        if(!vst[*it]) ddfs(*it);
    dead[p] = 1;
}

int main (){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++){
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        a--, b--; if(c == 0) G[a].PB(b), rG[b].PB(a);
        if(a == b && c == 0) dead[a] = 1; tG[a].PB(b);
    }
    kosaraju();
    for(int i = 0; i < cnt; i++){
        if(SZ(scc[i]) == 1) continue;
        FOR(it, scc[i]) dead[*it] = 1;
    }
    fill(vst, vst+n, 0);
    for(int i = 0; i < n; i++)
        if(!vst[i] && dead[i]) ddfs(i);
    for(int i = 0; i < n; i++)
        printf("%d\n", 1 - dead[i]);
}