hdu 6165 FFF at Valentine(tarjan縮點+拓撲排序)

FFF at Valentine

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 780    Accepted Submission(s): 387

Problem Description

At Valentine's eve, Shylock and Lucar were enjoying their time as any other couples. Suddenly, LSH, Boss of FFF Group caught both of them, and locked them into two separate cells of the jail randomly. But as the saying goes: There is always a way out , the lovers made a bet with LSH: if either of them can reach the cell of the other one, then LSH has to let them go.

The jail is formed of several cells and each cell has some special portals connect to a specific cell. One can be transported to the connected cell by the portal, but be transported back is impossible. There will not be a portal connecting a cell and itself, and since the cost of a portal is pretty expensive, LSH would not tolerate the fact that two portals connect exactly the same two cells.

As an enthusiastic person of the FFF group, YOU are quit curious about whether the lovers can survive or not. So you get a map of the jail and decide to figure it out.

Input Input starts with an integer T (T≤120), denoting the number of test cases.

For each case,

First line is two number n and m, the total number of cells and portals in the jail.(2≤n≤1000,m≤6000)

Then next m lines each contains two integer u and v, which indicates a portal from u to v. ∙a

Output If the couple can survive, print “I love you my love and our love save us!”

Otherwise, print “Light my fire!”

Sample Input

3 5 5 1 2 2 3 2 4 3 5 4 5 3 3 1 2 2 3 3 1 5 5 1 2 2 3 3 1 3 4 4 5  

Sample Output

Light my fire! I love you my love and our love save us! I love you my love and our love save us!  

tarjan算法詳解(大神部落格):http://www.cnblogs.com/uncle-lu/p/5876729.html 點選打開連結

題意: 問你一幅有向圖中能不能從一個點出發，一次走完所有的點

解析: 用tarjan縮點，将圖中的環都處理成點，再用拓撲排序，若一次入隊列有>1個點，則說明不行，否則可以

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
#define MAXN 1010
#define MAXM 6010

typedef struct node
{
	int u,v;
	int next;
}node;

int n,m,cnt,index;
node edge[MAXM];
int head[MAXN],ufset[MAXN],indegree[MAXN];
int DFN[MAXN],LOW[MAXN],visit[MAXN];
stack<int> ms;
vector<int> gg[MAXN];

void addEdge(int u,int v)
{
	edge[cnt].next=head[u];
	edge[cnt].u=u;
	edge[cnt].v=v;
	head[u]=cnt++;
}

void tarjan(int x)
{
	DFN[x]=LOW[x]=++index;   
	ms.push(x);   
	visit[x]=1;   //标記入棧
	for(int i=head[x];i!=-1;i=edge[i].next)
	{
		int v=edge[i].v;
		if(!DFN[v])   //如果這條邊沒有周遊過
		{
			tarjan(v);  //遞歸周遊他
			LOW[x]=min(LOW[x],LOW[v]);   //并将x加入到根節點比它小（入棧時間比它早）的樹中，若還是low[x]比較小，那麼x自己就是一棵一個節點的樹
		}
		else if(visit[v])   //如果這個點已經被周遊過且現在還在棧中，說明存在環
		{
			LOW[x]=min(LOW[x],DFN[v]);   //得到環的最開始的判定就是從這一步開始的，因為隻通過LOW[x]=min(LOW[x],LOW[v])，隻能從自己下面（即後搜的點中得到父節點資訊）
			//LOW[x]=min(LOW[x],LOW[v]);
		}                                  //而當自己連接配接的那條邊是構成環的那條邊時，就是通過這一步得到的，将自己現在的父節點的入棧時間low[x]與在自己之前已經入棧（周遊過）且還在棧中的節點的入棧時間比較
	}
	if(DFN[x]==LOW[x])  //任何一個強連通分量，必定是對原圖的深度優先搜尋樹的子樹
	{
		int u;
		do
		{
			u=ms.top();
			ms.pop();
			ufset[u]=x;  //一個環添加到一個并查集中
			visit[u]=0;

		}while(u!=x);
	}
}


int toposort()
{
	queue<int> mq;
	for(int i=1;i<=n;i++)
	{
		int b=ufset[i];
		if(indegree[b]==0&&visit[b]==0)
		{
			mq.push(b);
			visit[b]=1;
			if(mq.size()>1) return 0;
		}
	}

	while(mq.size())
	{
		int tmp=mq.front();
		mq.pop();
		int time=0;
		for(int i=0;i<gg[tmp].size();i++)
		{
			int v=gg[tmp][i];
			indegree[v]--;
			if(indegree[v]==0&&visit[v]==0)
			{
					mq.push(v);
					time++;
					visit[v]=1;
			}
			if(time>1) return 0;
			
		}
	}
	return 1;
}


int main()
{
	int t,a,b;
	scanf("%d",&t);
	while(t--)
	{
		memset(edge,0,sizeof(edge));
		memset(DFN,0,sizeof(DFN));
		memset(LOW,0,sizeof(LOW));
		memset(head,-1,sizeof(head));
		memset(ufset,-1,sizeof(ufset));

		cnt=index=0;
		scanf("%d%d",&n,&m);
		for(int i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			addEdge(a,b);
		}
		memset(visit,0,sizeof(visit));
		for(int i=1;i<=n;i++)   //縮點
			if(!DFN[i]) tarjan(i);

		memset(indegree,0,sizeof(indegree));
		memset(visit,0,sizeof(visit));
		for(int i=1;i<=n;i++)gg[i].clear();

		for(int i=0;i<m;i++)   //重建立圖
		{
			if(ufset[edge[i].u]!=ufset[edge[i].v])
			{
				gg[ufset[edge[i].u]].push_back(ufset[edge[i].v]);
				indegree[ufset[edge[i].v]]++;
			}
		}
		int flag=0;
		flag=toposort();

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

	}
	return 0;
}