HDU 6165 FFF at Valentine

• 題意：
  • 給定一個有向圖，n個點，m條邊，無自環，無重邊
  • 問：是否任意兩點A,B，滿足AB連通
• 規模：
  • 2<=n<=1000,m<=6000
  • T<120
• 類型：
  • 有向強連通，拓撲排序
• 分析：
  • 有向圖縮環後，拓撲排序一下，如果入度為0的點有多個，就無法連通
• 代碼：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN=;
const int MAXM=;
struct Edge{
    int to,next;
}edge[MAXM],edge2[MAXM];
int head[MAXN],head2[MAXN],tot,tot2;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];
int Index,top;
int scc;
bool Instack[MAXN];
int num[MAXN];
int in[MAXN],out[MAXN];
void addedge(int u,int v){
    edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void addedge2(int u,int v){
    edge2[tot2].to=v;edge2[tot2].next=head2[u];head2[u]=tot2++;
}
void Tarjan(int u){
    int v;
    Low[u]=DFN[u]=++Index;
    Stack[top++]=u;
    Instack[u]=true;
    for(int i=head[u];i!=-;i=edge[i].next){
        v=edge[i].to;
        if(!DFN[v]){
            Tarjan(v);
            if(Low[u]>Low[v])Low[u]=Low[v];
        }
        else if(Instack[v]&&Low[u]>DFN[v])
            Low[u]=DFN[v];
    }
    if(Low[u]==DFN[u]){
        scc++;
        do{
            v=Stack[--top];
            Instack[v]=false;
            Belong[v]=scc;
            num[scc]++;
        }
        while(v!=u);
    }
}
void solve(int N){
    memset(DFN,,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    memset(num,,sizeof(num));
    Index=scc=top=;
    for(int i=;i<=N;i++){
        if(!DFN[i])
            Tarjan(i);
    }
}

bool map2[MAXN][MAXN];
void build(int n){
    memset(map2,false,sizeof(map2));
    memset(in,,sizeof(in));
    memset(out,,sizeof(out));
    memset(head2,-,sizeof(head2));tot2=;
    for(int i=;i<=n;i++){
        for(int j=head[i];j!=-;j=edge[j].next){
            int v=edge[j].to;
            int a=Belong[i];
            int b=Belong[v];
            if(a==b)continue;
            if(!map2[a][b]){
                addedge2(a,b);
                map2[a][b]=true;
                in[b]++;out[a]++;
            }
        }
    }
}

void init(){
    tot=;
    memset(head,-,sizeof(head));
}

bool Top(){
    queue<int >q;
    while(!q.empty())q.pop();
    for(int i=;i<=scc;i++){
        if(in[i]==)q.push(i);
    }

    while(!q.empty()){
        if(q.size()!=)return false;
        int u=q.front();
        q.pop();
        for(int i=;i<=scc;i++){
            if(map2[u][i]==true) {
                in[i]--;
                if(in[i]==)q.push(i);
            }
        }
    }
    return true;
}

int n,m;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        for(int i=;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
        }
        solve(n);
        build(n);

        if(!Top()){printf("Light my fire!\n");}
        else printf("I love you my love and our love save us!\n");
    }

    return ;
}