「图论练习」easy

2014年12月20日4,2241

hzwer蒟蒻刚刚学了点图论，现在他面对一张有向图

他想问你：

1：最少选择多少个点，使得从这些点出发能遍历完整个图

2：最少添加多少条有向边，能使得整个图成为强连通图

输入格式

第一行n，m，n个点m条边

接下来m行，每行u，v

表示一条u到v的有向边

输出格式

两行，分别为两问答案

样例输入

5 3

1 2

2 3

3 4

样例输出

数据范围

20%的数据N<=20, M<=50

40%的数据N<=2000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

题解

第一问显然是入度为0的连通块个数

第二问，max{入度为0的连通块个数，出度为0的连通块个数}

特判连通块为1的情况

TAT第二问我想不出严格的证明，求神犇解答

大概是每个连通块，出度0的点，向其它连通块连边，使得形成一个环，其它的随便出度0连入度0？

唉反正我找不出反例暂且认为是正确的吧

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
int read()
{
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,cnt,top,scc,ind;
int last[10005],low[10005],dfn[10005],q[10005],bl[10005];
int in[10005],out[10005];
bool inq[10005];
struct edge{
	int to,next;
}e[50005];
void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void tarjan(int x)
{
	low[x]=dfn[x]=++ind;
	q[++top]=x;inq[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(!dfn[e[i].to])
		{
			tarjan(e[i].to);
			low[x]=min(low[x],low[e[i].to]);
		}
		else if(inq[e[i].to])
			low[x]=min(low[x],dfn[e[i].to]);
	if(low[x]==dfn[x])
	{
		scc++;
		int now=0;
		while(x!=now)
		{
			now=q[top--];inq[now]=0;
			bl[now]=scc;
		}
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	for(int x=1;x<=n;x++)
		for(int i=last[x];i;i=e[i].next)
			if(bl[x]!=bl[e[i].to])
				in[bl[e[i].to]]++,out[bl[x]]++;
	int t1=0,t2=0;
	for(int i=1;i<=scc;i++)
	{
		if(!in[i])t1++;
		if(!out[i])t2++;
	}
	printf("%d\n",t1);
	if(scc==1)puts("0");
	else printf("%d",max(t1,t2));
	return 0;
}

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#define ll long long

using namespace std;

int read()

{

int x=0;char ch=getchar();

while(ch>'9'||ch<'0')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int n,m,cnt,top,scc,ind;

int last[10005],low[10005],dfn[10005],q[10005],bl[10005];

int in[10005],out[10005];

bool inq[10005];

struct edge{

int to,next;

}e[50005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

void tarjan(int x)

{

low[x]=dfn[x]=++ind;

q[++top]=x;inq[x]=1;

for(int i=last[x];i;i=e[i].next)

if(!dfn[e[i].to])

{

tarjan(e[i].to);

low[x]=min(low[x],low[e[i].to]);

}

else if(inq[e[i].to])

low[x]=min(low[x],dfn[e[i].to]);

if(low[x]==dfn[x])

{

scc++;

int now=0;

while(x!=now)

{

now=q[top--];inq[now]=0;

bl[now]=scc;

}

int main()

{

n=read();m=read();

for(int i=1;i<=m;i++)

{

int u=read(),v=read();

insert(u,v);

}

for(int i=1;i<=n;i++)

if(!dfn[i])tarjan(i);

for(int x=1;x<=n;x++)

for(int i=last[x];i;i=e[i].next)

if(bl[x]!=bl[e[i].to])

in[bl[e[i].to]]++,out[bl[x]]++;

int t1=0,t2=0;

for(int i=1;i<=scc;i++)

{

if(!in[i])t1++;

if(!out[i])t2++;

}

printf("%d\n",t1);

if(scc==1)puts("0");

else printf("%d",max(t1,t2));

return 0;

}

« 「BZOJ2893」征服王「图论练习」medium »

hhhhggg

其实第二问是原题。。
LiveArchive 4287
https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2288
刘汝佳训练指南中也出现了这道题目。
训练指南：”证明部分留给读者完成“
（我也想知道怎么证QAQ）

hzwer.com _ Home | http://hzwer.com

「图论练习」easy

分类目录

热门文章

Myfriends

近期评论