hdu 6165 FFF at Valentine (數學思想 || 縮點)

數學思想做這個題，就有點套路了。這個題目要求的是什麼的呢？一個點能到其他所有的點。如果這樣的以下條件肯定會成立，假設點1 2 3 4 5；

1是根節點，有一條路徑1->2->3->4->5;

是以1 2 3 4 5 .                1代表的是有路徑，0代表沒有路徑，如果1->2有路徑，把（1,2）（2,1）都标記了                 

    1 1 1 1 1 1                    這個圖肯定全為1.對每個點進行深搜，最壞的情況是，所有的點成為一個大的環

    2 0 1 1 1 1                   如果120組資料全都是這種情況，會逾時3-6秒，但是不存在的，1800ms過了

    3 0 0 1 1 1

    4 0 0 0 1 1

    5 0 0 0 0 1

#include<bits/stdc++.h>
using namespace std;
#define  pb push_back
vector <int>g[1005];
bool flag[1005][1005];
bool vis[1005];
int cnt,n;
void dfs(int u)
{
    for(int j=0;j<g[u].size();j++)
    {
        int v=g[u][j];
        flag[cnt][v]=1;
        flag[v][cnt]=1;
        if(!vis[v])
        {
            vis[v]=1;
            dfs(v);
        }
    }
}
void solve()
{

    for(int i=1;i<=n;i++)
    {
    memset(vis,0,sizeof(vis));
       cnt=i;
       vis[i]=1;
       dfs(i);
       flag[i][i]=1;
    }
}
int main()
{
 //freopen("in.txt","r",stdin);
 //  freopen("out.txt","w",stdout);
 int t;
 scanf("%d",&t);
 while(t--)
 {
     int m,a,b;

     memset(flag,0,sizeof(flag));
     scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)g[i].clear();
     for(int i=1;i<=m;i++)
     {
         scanf("%d%d",&a,&b);
         g[a].pb(b);
     }
     solve();
     int ans=1;
     for(int i=1;i<=n;i++)
        {for(int j=1;j<=n;j++)
         {//cout<<flag[i][j]<<" ";
        if(!flag[i][j])ans=0;
        }
        //cout<<endl;
        }
        if(ans)printf("I love you my love and our love save us!\n");
        else puts("Light my fire!");
 }
    return 0;
}
           

強聯通分量

#include<bits/stdc++.h>
using namespace std;
#define  pb push_back
const int maxn=1100;
int V;              //頂點數
vector<int>G[maxn]; //圖的鄰接表表示
vector<int>rG[maxn];//把邊反向後的圖
vector<int>vs;      //後序周遊順序的頂點清單
bool used[maxn];   //通路标記
int cmp[maxn];     //所屬強連通分量的拓撲序
int in[maxn];
vector<int>g[maxn];
queue<int >q;
void init()
{
    for(int i=0; i<maxn; i++)
        G[i].clear(),rG[i].clear(),g[i].clear();
    while(!q.empty())q.pop();
}
void add_edge(int from,int to)
{
    G[from].pb(to);
    rG[to].pb(from);
}
void dfs(int u)
{
    used[u]=true;
    for(int i=0; i<(int)G[u].size(); i++)
    {
        if(!used[G[u][i]])dfs(G[u][i]);
    }
    vs.push_back(u);
}
void rdfs(int u,int k)
{
    used[u]=true;
    cmp[u]=k;
    for(int i=0; i<(int)rG[u].size(); i++)
    {
        if(!used[rG[u][i]])rdfs(rG[u][i],k);
    }
}
int scc()
{
    memset(used,0,sizeof(used));
    vs.clear();
    for(int v=1; v<=V; v++)
        if(!used[v])dfs(v);
    memset(used,0,sizeof(used));
    int k=0;
    for(int i=vs.size()-1; i>=0; i--)
    {
        if(!used[vs[i]])rdfs(vs[i],k++);
    }

    //以上為強聯通分量模闆，in數組處理縮點
    memset(in,0,sizeof(in));
    for(int i=1; i<=V; i++)
        for(int j=0; j<(int)G[i].size(); j++)
        {
            int v=G[i][j];
          //  cout<<v<<endl;
            if(cmp[i]!=cmp[v])
            {
                in[cmp[v]]++;
                g[cmp[i]].pb(cmp[v]);
            }
        }
    return k;
}
int main()
{
//freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
//ios::sync_with_stdio(false);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        int m,a,b;
        scanf("%d%d",&V,&m);
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            add_edge(a,b);
        }
        int k=scc();
        int flag=0;
        for(int i=0; i<k; i++)
        {
            if(in[i]==0)flag++,q.push(i);
            if(flag==2)break;
        }

        if(flag<2)
        {

            while(!q.empty())
            {
                int p=q.front();
                q.pop();
                flag=0;
                for(int i=0; i<(int)g[p].size(); i++)
                {
                    int v=g[p][i];
                    in[v]--;
                    if(in[v]==0)flag++,q.push(v);
                }
                if(flag>=2)break;
            }
        }
        if(flag<2) puts("I love you my love and our love save us!");
        else  puts("Light my fire!");
    }
    return 0;
}