description

给定由 n 个点 m 条边组成的无向连通图，保证没有重边和自环。

你需要找出所有边，满足这些边恰好存在于一个简单环中。一个环被称为简单环，当且仅当它包含的所有点都只在这个环中被经过了一次。

注意到这些边可能有很多条，你只需要输出他们编号的异或和即可。

analysis

然而复习了一波\(tarjan\)，其实这个简单环就是求点双
求出每个点双，判断点双里的边数是否等于点双点数
这个不能暴力求，方法就是记录每个点有多少条返祖边、返祖边的异或和
因为这些返祖边指向的点和该点本身肯定在同一个点双中
感觉\(tarjan\)这种东西还是记下好一点，不过跑得好慢很奇怪

code

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<vector>

#define MAXN 1000005

#define MAXM 2000005

#define ll int

#define reg register ll

#define max(x,y) ((x>y)?(x):(y))

#define min(x,y) ((x<y)?(x):(y))

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

#define rep(i,a) for (reg i=last[a];i;i=next[i])

using namespace std;

ll last[MAXM],next[MAXM],tov[MAXM],id[MAXM];

ll dfn[MAXN],low[MAXN],stack[MAXN],where[MAXN],num[MAXN],xorval[MAXN];

ll n,m,tot,top,ans,sum,root=1,size;

bool bz[MAXN],cut[MAXN];

vector<ll>v[MAXN];

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

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

	return x*f;

}

inline void link(ll x,ll y,ll z){next[++tot]=last[x],last[x]=tot,tov[tot]=y,id[tot]=z;}

inline void tarjan(ll x)

{

	dfn[x]=low[x]=++tot,bz[x]=1,stack[++top]=x;ll flag=0;

	rep(i,x)if (!dfn[tov[i]])

	{

		tarjan(tov[i]),low[x]=min(low[x],low[tov[i]]);

		if (low[tov[i]]>=dfn[x])

		{

			++flag,++sum;ll tmp,total=0,xorsum=0;

			if (x!=root || flag>1)cut[x]=1;

			do

			{

				tmp=stack[top--],v[sum].push_back(tmp),total+=num[tmp],xorsum^=xorval[tmp];

			}

			while (tmp!=tov[i]);

			v[sum].push_back(x);

			if (total==v[sum].size())ans^=xorsum;

		}

	}

	else

	{

		if (dfn[tov[i]]>dfn[x])continue;

		++num[x],xorval[x]^=id[i];

		low[x]=min(low[x],dfn[tov[i]]);

	}

}

int main()

{

	freopen("graph.in","r",stdin);

	freopen("graph.out","w",stdout);

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

	fo(i,1,m)

	{

		ll x=read(),y=read();

		link(x,y,i),link(y,x,i);

	}

	tot=0,tarjan(1);

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

	return 0;

}

巴特西

【JZOJ6409】困难的图论

description

analysis

code

最新文章

热门文章