luogu P2812 校园网络【[USACO]Network of Schools加强版】|Tarjan

题目背景

浙江省的几所OI强校的神犇发明了一种人工智能，可以AC任何题目，所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空，他们来找你帮助他们。

题目描述

共有n所学校（n<=10000）已知他们实现设计好的网络共m条线路，为了保证高速，网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机母鸡，能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机母鸡都可以使别的学校使用上软件。

输入格式

第一行一个整数n。

接下来n行每行有若干个整数，用空格空格隔开。

第i-1行的非零整数x，表示从i到x有一条线路。以0作为结束标志。

输出格式

第一行一个整数表示问题1的答案。

第二行回答问题2.

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<vector>

#define ll long long

using namespace std;

const int N=1e6+10,M=5*N;

int next[M],head[N],go[M],tot;

inline void add(int u,int v){

	next[++tot]=head[u];head[u]=tot;go[tot]=v;

}

int dfn[N],low[N],st[N],co[N],num,col,top;

void Tarjan(int u){

	dfn[u]=low[u]=++num;

	st[++top]=u;

	for(int e=head[u];e;e=next[e]){

		int v=go[e];

		if(!dfn[v]){

			Tarjan(v);

			low[u]=min(low[u],low[v]);

		}

		else

		if(!co[v])

		low[u]=min(low[u],dfn[v]);

	}

	if(dfn[u]==low[u]){

		co[u]=++col;

		while(st[top]!=u){

			co[st[top]]=col;

			--top;

		}

		--top;

	}

}

struct E{

	int u,v;

}e[M];

int sum=0,in[N],out[N];

int main(){

	int n;

	cin>>n;

	for(int i=1,x;i<=n;i++){

		scanf("%d",&x);

		while(x!=0){

			add(i,x);

			e[++sum]=(E){i,x};

			scanf("%d",&x);

		}

	}

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

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

	for(int i=1;i<=sum;i++){

		if(co[e[i].u]!=co[e[i].v])

		in[co[e[i].v]]++,out[co[e[i].u]]++;

	}

	int ans=0,op=0;

	for(int i=1;i<=col;i++){

		if(in[i]==0)ans++;

		if(out[i]==0)op++;

	}

	printf("%d\n%d",ans,op);

}

巴特西

luogu P2812 校园网络【[USACO]Network of Schools加强版】|Tarjan

题目背景

题目描述

输入格式

输出格式

最新文章

热门文章