【HDU6165】【多校】FFF at Valentine
题目大意就是图中选任意两点，都至少有一个点能到达另一个点。
初步想一下，在环上的点肯定是能互相到达的，所以环缩成点，然后整个图就成了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;
}
评论 (0)
