首页 > 代码库 > UVA 11770 Lighting Away

UVA 11770 Lighting Away

2024-07-14 00:33:53   219人阅读

RunID

User

Problem

Result

Memory

Time

Language

Length

Submit Time

2482977

zhyfzy

J

Accepted

0 KB

138 ms

C++ 4.8.2

2322 B

2014-07-24 15:18:54

【题目大意】

一个有向图，每对一个结点操作，就可以触发连锁反应，使得该结点及它直接或间接指向的点均获得标记，问至少需要操作多少个结点使得所有结点获得标记

【题解】

缩点+DFS

首先能想到入度为0的点一定需要操作，但是操作完所有入度为0的点不一定使所有结点获得标记，比如存在环的情况，因此，我们需要先缩点，缩点使用Tarjan算法，详见代码，缩点之后直接统计入度为0的点有多少个即可。

代码采用链式向前星的存储结构

【代码】

#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<stack>#define P 20000#define E 200000using namespace std;int i,j,k,n,T,ans,K,m,x,y,indexs,nn,mm;int ru[P],head[P],head2[P],dfn[P],low[P],instack[P],belong[P];bool b[E];stack <int> tar; struct node{	int from;	int to;	int next;}map[E],map2[E];void addedge(int num,int x,int y){	map[num].from=x;	map[num].to=y;	map[num].next=head[x];	head[x]=num;}void addedge2(int num,int x,int y){	//printf("NewEdge %d %d\n",x,y); 		ru[y]++;	map2[num].from=x;	map2[num].to=y;	map2[num].next=head2[x];	head2[x]=num;}void dfs(int p){	for (int i=head2[p];i!=-1;i=map2[i].next)	{		if (!b[map2[i].to])		{			b[map2[i].to]=true;			dfs(map2[i].to);		}	}}void tarjan(int k){    int p;    tar.push(k);    instack[k]=1;    dfn[k]=low[k]=++indexs;    for(int j=head[k];j!=-1;j=map[j].next)    {        p=map[j].to;        if (instack[p]) 		{			low[k]=min(low[k],dfn[p]);		}        else 		if(dfn[p]==-1)        {            tarjan(p);            low[k]=min(low[k],low[p]);        }    }    if(low[k]==dfn[k])    {        nn++;        do        {            j=tar.top();            tar.pop();            instack[j]=0;            belong[j]=nn;        }while(j!=k);    }}void build_new_map(){    for(int i=1;i<=m;i++)    {        if(belong[map[i].from]==belong[map[i].to]) 			continue;        addedge2(++mm,belong[map[i].from],belong[map[i].to]);    }}void build_map(){	scanf("%d%d",&n,&m);	for (i=1;i<=m;i++)	{		scanf("%d%d",&x,&y);		addedge(i,x,y);	}	memset(dfn,-1,sizeof(dfn));	memset(low,-1,sizeof(low));	memset(instack,0,sizeof(instack));	indexs=0;nn=0;		for (i=1;i<=n;i++) belong[i]=i;		for (i=1;i<=n;i++)	{		if (dfn[i]==-1)			tarjan(i);	}		build_new_map();}int main(){	scanf("%d",&T);	while (++K<=T)	{		memset(map,-1,sizeof(map));		memset(head,-1,sizeof(head));		memset(map2,-1,sizeof(map2));		memset(head2,-1,sizeof(head2));		memset(b,0,sizeof(b));		memset(ru,0,sizeof(ru));		ans=0;mm=0;nn=0;				build_map();				for (i=1;i<=nn;i++)		{			if (!ru[i])			{				ans++;				b[i]=true;				dfs(i);			}		}				for (i=1;i<=nn;i++)		{			if (!b[i])			{				ans++;			 	b[i]=true;				dfs(i);			}		}		printf("Case %d: %d\n",K,ans);	}}

　　


联系
我们