【HDU6165】【多校】FFF at Valentine

Zarxdy34 posted @ 2017年9月05日 17:11 in HDU with tags 强连通分量 , 47 阅读
    题目大意就是图中选任意两点,都至少有一个点能到达另一个点。
 
    初步想一下,在环上的点肯定是能互相到达的,所以环缩成点,然后整个图就成了DAG。
 
    接下来想想似乎图只能是一条链,如果出现了分支就不行了,因为分支之间无法互相到达。
 
    不过这是有明显的反例的,比如1号点连2、3、4、5号点,然后2,3,4,5号点依次连接。
 
    于是我加了一个这种情况的特判就过了。
 
    后来发现只要不断删去出度为0的点,如果同时有两个出度为0的点就判失败就好了...
 
 
#include <bits/stdc++.h>
using namespace std;
const int maxn=1010,maxe=6010;

int head[maxn],nxt[maxe],E[maxe],Ecnt;
int head2[maxn],nxt2[maxe],E2[maxe],Ecnt2;
int DFN[maxn],Low[maxn],Index;
int Stack[maxn],top;
bool Instack[maxn];
int ID[maxn],cnt;
int vis[maxn];
int deg[maxn];
int n,m;

void Add_Edge(int u,int v) {nxt[++Ecnt]=head[u];head[u]=Ecnt;E[Ecnt]=v;}
void Add_Edge2(int u,int v) {nxt2[++Ecnt2]=head2[u];head2[u]=Ecnt2;E2[Ecnt2]=v;}

void Tarjan(int x)
{
    DFN[x]=Low[x]=++Index;
    Instack[x]=true;
    Stack[++top]=x;
    for (int i=head[x];i;i=nxt[i])
        if (!DFN[E[i]]) Tarjan(E[i]),Low[x]=min(Low[x],Low[E[i]]);
        else if (Instack[E[i]]) Low[x]=min(Low[x],DFN[E[i]]);
    if (DFN[x]==Low[x])
    {
        cnt++;
        while (Instack[x])
        {
            int u=Stack[top--];
            Instack[u]=false;
            ID[u]=cnt;
        }
    }
}

bool DFS(int x)
{
	vis[x]=1;
	int ne=0;
	for (int i=head2[x];i;i=nxt2[i]) if (ne==0 || deg[E2[i]]<deg[E2[ne]]) ne=i;
	if (ne==0) return true;
	if (!DFS(E2[ne])) return false;
	for (int i=nxt2[ne];i;i=nxt2[i]) if (!vis[E2[i]]) return false;
	return true;
}

bool Check()
{
	memset(head2,0,sizeof(head2));
	memset(deg,0,sizeof(deg));
	memset(vis,0,sizeof(vis));
	Ecnt2=0;
	for (int i=1;i<=n;i++)
	for (int j=head[i];j;j=nxt[j]) if (ID[i]!=ID[E[j]])
		Add_Edge2(ID[i],ID[E[j]]),deg[ID[E[j]]]++;
	int d0=0;
	for (int i=1;i<=cnt && d0==0;i++) if (deg[i]==0) d0=i;
	for (int i=d0+1;i<=cnt;i++) if (deg[i]==0) return false;
	return DFS(d0);
}

int main()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		memset(head,0,sizeof(head));
		memset(DFN,0,sizeof(DFN));
		memset(Low,0,sizeof(Low));
		Ecnt=Index=cnt=0;
		scanf("%d%d",&n,&m);
		for (int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),Add_Edge(u,v);
		for (int i=1;i<=n;i++) if (!DFN[i]) Tarjan(i);
		if (!Check()) printf("Light my fire!\n");else printf("I love you my love and our love save us!\n");
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1