正题

题目链接:https://www.luogu.com.cn/problem/AT3945

题目大意

\(n\)个点\(m\)条边的一张图，对于每条边求它翻转后强连通分量数量是否变化。

\(1\leq n\leq 1000,1\leq m\leq 2\times 10^5\)

解题思路

对于一条\((x,y)\)的边。

如果原来\(y\)能走到\(x\)，那么考虑现在是否强连通分量是否减少，就是说如果存在一条\(x->y\)的路径不经过这条边那么不变，否则减少。
如果原来\(y\)不能走到\(x\)，那么考虑现在强连通分量是否增加，那么如果存在一条\(x->y\)的路径不经过这条边那么就会产生一个新的强连通分量。

考虑每一个\(x\)能否走到\(y\)，这个直接暴力\(O(nm)\)预处理就好了。

然后考虑对于每条边\(x,y\)，\(x\)能否不经过这条边走到\(y\)，从\(x\)开始\(dfs\)，记录出去的第一条边，然后如果到一个点有两种不同情况那么标记即可。

时间复杂度\(O(nm)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int N=1e3+10,M=2e5+10;

int n,m,f[N][N],g[N][N],X[M],Y[M];

vector<int> a[N];

void step(int x,int *v){

	if(v[x])return;v[x]=1;

	for(int i=0;i<a[x].size();i++)

		step(a[x][i],v);

}

void calc(int x,int *v){

	if(v[x]==1)return;v[x]=1;

	for(int i=0;i<a[x].size();i++)

		calc(a[x][i],v);

	return;

}

void dfs(int x,int *v,int pos){

	if(v[x]>0)return;

	else if(v[x]<0){

		if((-v[x])==pos)return;

		else v[x]=1;

	}

	else if(!v[x])v[x]=-pos;

	for(int i=0;i<a[x].size();i++)

		if(v[x]==1)calc(a[x][i],v);

		else dfs(a[x][i],v,pos);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

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

		int x,y;

		scanf("%d%d",&x,&y);

		a[x].push_back(y);X[i]=x;Y[i]=y;

	}

	for(int i=1;i<=n;i++)step(i,f[i]);

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

		g[x][x]=1;

		for(int i=0;i<a[x].size();i++)

			dfs(a[x][i],g[x],i+1);

	}

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

		if(f[Y[i]][X[i]]){

			if(g[X[i]][Y[i]]==1)puts("same");

			else puts("diff");

		}

		else{

			if(g[X[i]][Y[i]]==1)puts("diff");

			else puts("same");

		}

	}

	return 0;

}

巴特西

AT3945-[ARC092D]Two Faced Edges【dfs】

正题

题目大意

解题思路

code

最新文章

热门文章