題意：就任意兩個點能否到達；

解題思路：首先將圖簡化，比如假設(shè)圖里有一個環(huán)，那么，這環(huán)內(nèi)兩個點肯定是能相互到達的，那么就不用考慮這環(huán)內(nèi)的點了，很簡單就想到用tarjan算法將環(huán)縮成一個點，然后就是判斷縮完點后的圖內(nèi)任意兩點能否互相到達了，能互相到達一定是有路徑連接所有點的，就通過拓撲排序了，如果同一層的兩點或以上的入度在排序時都為0時那么肯定不能到達，因為沒有路徑連接這兩個點，這道題屬于模板型的題，只要思路正確，是能寫出來的，貌似還有暴力dfs的寫法，還沒去看；

代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int MAXN=2e5+5;
const int MAXM=5e5+5;
int head[MAXN],tot;
int low[MAXN],dfn[MAXN],sta[MAXN],bel[MAXN];//bel數(shù)組的值是1~scc
int index,top;
int scc;//強連通分量的個數(shù)
bool instack[MAXN];
int num[MAXN];//各個強連通分量包含點的個數(shù)，數(shù)組編號1~scc
//num數(shù)組不一定需要，結(jié)合實際情況
int n,m;

struct Edge
{
??? int from,to,nxt;
}edge[MAXM];

void addedge(int u,int v)
{
??? edge[tot].from=u;
??? edge[tot].to=v;
??? edge[tot].nxt=head[u];
??? head[u]=tot++;
}//鏈式前向星存圖；

void tarjan(int u)
{
??? int v;
??? low[u]=dfn[u]=++index;
??? sta[top++]=u;
??? instack[u]=true;
??? for(int i=head[u];i!=-1;i=edge[i].nxt)
??? {
??????? 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=sta[--top];
??????????? instack[v]=false;
??????????? bel[v]=scc;
??????????? num[scc]++;
??????? }while(v!=u);
??? }
}//tarjan算法算強聯(lián)通圖；

void solve(int n)
{
??? memset(dfn,0,sizeof(dfn));
??? memset(instack,false,sizeof(instack));
??? memset(num,0,sizeof(num));
??? index=scc=top=0;
??? for(int i=1;i<=n;i++)
??? {
??????? if(!dfn[i]) tarjan(i);
??? }
}

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

int in[MAXN];
vector<int> G[MAXN];
void suodian()
{
??? memset(in,0,sizeof(in));
??? for(int i=1;i<=scc;i++) G[i].clear();
??? for(int i=0;i<m;i++)
??? {
??????? int u=bel[edge[i].from];
??????? int v=bel[edge[i].to];
??????? if(u!=v)
??????? {
??????????? G[u].push_back(v);
??????????? in[v]++;
??????? }
??? }
??? int cnt=0,p;
??? for(int i=1;i<=scc;i++)
??? {
??????? if(in[i]==0) {cnt++;p=i;}
??? }
??? if(cnt>=2) printf("Light my fire!\n");
??? else
??? {
??????? queue<int> q;
??????? while(!q.empty()) q.pop();
??????? q.push(p);
??????? bool flag=true;
??????? while(!q.empty())
??????? {
??????????? int fs=q.front();
??????????? q.pop();
??????????? int du=0;
??????????? int sz=G[fs].size();
??????????? for(int i=0;i<sz;i++)
??????????? {
??????????????? int to=G[fs][i];
??????????????? in[to]--;
??????????????? if(in[to]==0)
??????????????? {
??????????????????? du++;
??????????????????? q.push(to);
??????????????? }
??????????? }
??????????? if(du>=2) {flag=false;break;}
??????? }
??????? if(flag) printf("I love you my love and our love save us!\n");
??????? else printf("Light my fire!\n");
??? }
}//縮點后的拓撲排序；

int main()
{

??? int T;
??? scanf("%d",&T);
??? while(T--)
??? {
??????? scanf("%d%d",&n,&m);
??????? init();
??????? int u,v;
??????? for(int i=1;i<=m;i++)
??????? {
??????????? scanf("%d%d",&u,&v);
??????????? addedge(u,v);
??????? }
??????? solve(n);
// cout<<scc<<endl;
// for(int i=1;i<=n;i++)
// {
// cout<<bel[i]<<endl;
// }
// cout<<num[1]<<" "<<num[2]<<endl;
??????? suodian();
??? }
??? return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/huangdao/p/7726246.html

總結(jié)

以上是生活随笔為你收集整理的hdu6165（拓扑排序+tarjan缩点）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。