连通分量

强连通分量（有向图）

求法：tarjan

例题

https://www.luogu.org/problemnew/show/P2863
https://www.luogu.org/problemnew/show/P2341
连通分量
Description
我们已知n对夫妻的婚姻状况，称第i对夫妻的男方为Bi，女方为Gi。若某男Bi与某女Gj曾经交往过（无论是大学，高中，亦或是幼儿园阶段，i≠j），则当某方与其配偶（即Bi与Gi或Bj与Gj）感情出现问题时，他们有私奔的可能性。不妨设Bi和其配偶Gi感情不和，于是Bi和Gj旧情复燃，进而Bj因被戴绿帽而感到不爽，联系上了他的初恋情人Gk……一串串的离婚事件像多米诺骨牌一般接踵而至。若在Bi和Gi离婚的前提下，这2n个人最终依然能够结合成n对情侣，那么我们称婚姻i为不安全的，否则婚姻i就是安全的。给定所需信息，你的任务是判断每对婚姻是否安全。

思路

经过一番思考，我们发现一个人只有一个婚姻关系，以及一个情侣关系。如果破坏他的婚姻关系，那么一定要在和他的情侣关系在一起，也就是说如果一对夫妻在一个强连通分量里，就会有二种不同的方式互相到达
所以我们夫妻关系男向女，情侣女向男连边，跑tarjan

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map> 
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
inline int read(){
	char ch=' ';int f=1;int x=0;
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=10100;
const int M=500100;
map<string,int> ma;
struct node
{
	int v,nxt;
}edge[M];
int head[N],cnt;
void add(int u,int v)
{
	cnt++;
	edge[cnt].v=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
int dfn[N],low[N],t=0;
int belong[N],cc=0;
bool ins[N];
int s[N],top=0;
void dfs(int u)
{
	dfn[u]=low[u]=++t;
	ins[u]=true;s[++top]=u;
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int v=edge[i].v;
		if(!dfn[v])
		{
			dfs(v);
			low[u]=min(low[v],low[u]);
		}
		else if(ins[v])
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		cc++;
		while(s[top]!=u)
		{
			belong[s[top]]=cc;
			ins[s[top]]=false;
			top--;
		}
		belong[u]=cc;
		ins[u]=false;
		top--;
	}
}
int main()
{
	int n=read();
	string str;
	for(int i=1;i<=n;i++)
	{
		cin>>str;ma[str]=i;
		cin>>str;ma[str]=i+n;
		add(i,i+n);
	}
	int m=read();
	for(int i=1;i<=m;i++)
	{
		cin>>str;int u=ma[str];
		cin>>str;int v=ma[str];
		add(v,u);
	}
	for(int i=1;i<=(n<<1);i++)
	{
		if(!dfn[i])
		{
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(belong[i]==belong[i+n])
		{
			cout<<"Unsafe"<<endl;
		}
		else
		{
			cout<<"Safe"<<endl;
		}
	}
	return 0;
}

双连通分量（无向图）

割点和桥