HDU6165 FFF at Valentine（并查集+tarjan縮點+拓撲排序）

題目：

<—傳送門

思路：剛開始用bfs，dfs暴搜T了n發，然後換了個思路用拓撲排序做然後又wa了n發。。。看了官方題解才想到思路有漏洞，順便學了新姿勢縮點。主要是判斷兩個點之間是否有路徑，如果拓撲排序目前層存在兩個及以上入度為0的點，那麼這些點一定不存在通路。直接拓撲的話會碰到強聯通子圖，是以要把強聯通子圖都縮成一個點，然後建立一張圖，跑一遍拓撲排序判斷一下，就能得出答案。多加了一個并查集判斷給的圖是不是連通圖，不是的話直接Light my fire!，就不用做後面的了。

下面是代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<stack> 
#include<vector>
#include<algorithm>
#define N 1010
#define INF 0x3f3f3f3f
#define LL long long
#define EPS 1e-8
using namespace std;

struct point{
    int num,k;
    friend bool operator< (point a,point b)
    {
        return a.num<b.num;
    }
}p[N];

vector<int> g[N];   //舊圖
set<int> g_new[N];  //新圖
int n,m,xb[N];
int pa[N];
int dfn[N],low[N],tot,cnt;
bool vis[N];
stack<int> s;

void tarjan(int u)
{
    dfn[u]=low[u]=++tot;
    s.push(u);
    vis[u]=true;
    for(int i=;i<g[u].size();i++)
    {
        int &tmp=g[u][i];
        if(!dfn[tmp])
        {
            tarjan(tmp);
            low[u]=min(low[u],low[tmp]);
        }
        else if(vis[tmp])
        {
            low[u]=min(low[u],dfn[tmp]);
        }
    }
    if(low[u]==dfn[u])  //縮點
    {
        cnt++;
        int tmp;
        do{
            tmp=s.top();
            vis[tmp]=false;
            s.pop();
            pa[tmp]=cnt;
        }while(tmp!=u);
    }
} 

void init()   //初始化
{    
    for(int i=;i<=n;i++)    
    {    
        pa[i]=i;
        p[i].num=,p[i].k=i;
    }   
    cnt=tot=;
    memset(vis,false,sizeof(vis));
    memset(dfn,,sizeof(dfn));
    memset(low,,sizeof(low));  
}    

void clear_g()  //删除建的邊
{
    for(int i=;i<=n;i++)
        g[i].clear();
    for(int i=;i<=cnt;i++)
        g_new[i].clear();
}

int findset(int v)    
{    
    int t1,t2=v;    
    while(v!=pa[v])    
        v=pa[v];    
    while(t2!=pa[t2])          
    {    
        t1=pa[t2];    
        pa[t2]=v;    
        t2=t1;    
    }    
    return v;    
}   

void union_nodes(int a, int b)    
{    
    int a1=findset(a);    
    int b1=findset(b);  
    if(a1!=b1)     
    {  
        pa[a1]=b1;      
    }  
}   

bool sol()      //拓撲排序得出答案
{
    int k=;
    while(k<=cnt)
    {
        sort(p+k,p+cnt+); 
        //cout<<p[k].k<<endl;
        if(p[k].num>) return true;
        if(k<cnt&&p[k].num==p[k+].num) return false;
        for(int i=k+;i<=cnt;i++)
            xb[p[i].k]=i;
        p[k].num=-;
        for(set<int>::iterator it=g_new[p[k].k].begin();it!=g_new[p[k].k].end();it++)
        {
            p[xb[*it]].num--;
        }
        k++;
    }
    return true;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init(); 
        int u,v;
        for(int i=;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            union_nodes(u,v);
            g[u].push_back(v);
        }
        bool flag=true;
        for(int i=;i<=n;i++) //并查集判斷是否為連通圖
        {
            if(findset(i)!=findset())
            {
                flag=false;
                break;
            }
        }
        if(!flag) 
        {
            printf("Light my fire!\n");
            clear_g();
            continue;
        }
        for(int i=;i<=n;i++)
        {
            if(!dfn[i])
                tarjan(i);
        }
        //cout<<cnt<<endl;
        for(int i=;i<=n;i++)  //建新圖
        {
            //cout<<pa[i]<<endl;
            for(int j=;j<g[i].size();j++)
            {
                int &tmp=g[i][j];
                if(pa[tmp]!=pa[i])
                    g_new[pa[i]].insert(pa[tmp]);
            }
        }
        for(int i=;i<=cnt;i++)  //計算入度
        {
            //cout<<i<<' '<<g_new[i].size()<<endl;
            for(set<int>::iterator it=g_new[i].begin();it!=g_new[i].end();it++)
            {
                p[*it].num++;
                //cout<<*it<<endl;
            }
        }
        /*for(int i=1;i<=cnt;i++)
            cout<<p[i].k<<' '<<p[i].num<<endl;*/
        if(sol()) printf("I love you my love and our love save us!\n");
        else printf("Light my fire!\n");
        clear_g();
    }
}