day48-安博施

T1 CF555E Case of Computer Network

给定一张 n 个点 m 条边的无向图。
给定 q 组有向点对(s,t)。
询问是否存在使得所有 s 都能到达 t 的无向图中每条边的定向方案。
(n,m,q le 2 imes 10^5)

solution

其实吧，这题没有想象中那么难。

先(Tarjan) 求割边，缩点，然后得到一棵树。

对于一个询问((u , v))。

若u，v在同一个边双中一定存在一种方法使得这个边双的中的点两两互达，(边双中有环嘛。。)

若不在一个联通块里，(不在一棵树里)，那么肯定无解。

若都在一个树上就，将这条路劲上的边都打上一个标记，即可，具体实现可以用树上差分的方法。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
inline int read()
{
	register int x = 0 , f = 0; register char c = getchar();
	while(c < '0' || c > '9') f |= c == '-' , c = getchar();
	while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48) , c = getchar();
	return f ? -x : x;
}
int n , m , q , cnt = 1 , dfn_id , col_id , tag_id;
int head[N] , dfn[N] , vis[N << 1] , low[N] , col[N] , tag[N] , d[N] , s1[N] , s2[N] , f[N][20];
vector<int> G[N];
struct edge { int v , nex; }e[N << 1];
inline void add(int u , int v) { e[++cnt].v = v; e[cnt].nex = head[u]; head[u] = cnt; }

void Tarjan(int x , int f)
{
	dfn[x] = low[x] = ++dfn_id;
	for(int i = head[x] , v; i ; i = e[i].nex) if(i != f)
	{
		v = e[i].v;
		if(!dfn[v]) 
		{
			Tarjan(v , i ^ 1) , low[x] = min(low[x] , low[v]);
			if(low[v] > dfn[x]) vis[i] = vis[i ^ 1] = 1;
		}
		else low[x] = min(low[x] , dfn[v]);
	}
}

void dfs1(int x)
{
	col[x] = col_id;
	for(int i = head[x] ; i ; i = e[i].nex) if(!col[e[i].v] && !vis[i]) dfs1(e[i].v);
}

void dfs2(int x)
{
	tag[x] = tag_id;
	for(auto v : G[x]) if(v != f[x][0]) 
	{
		f[v][0] = x; d[v] = d[x] + 1;
		for(int i = 1 ; i < 20 ; ++i) f[v][i] = f[f[v][i-1]][i-1];
		dfs2(v);
	}
}

int LCA(int x , int y)
{
	if(d[x] < d[y]) swap(x , y);
	for(int i = 19 ; ~i ; --i) if(d[f[x][i]] >= d[y]) x = f[x][i];
	if(x == y) return x;
	for(int i = 19 ; ~i ; --i) if(f[x][i] != f[y][i]) x = f[x][i] , y = f[y][i];
	return f[x][0];
}

bool check(int x)
{
	for(auto v : G[x]) if(v != f[x][0])
	{
		if(!check(v) || (s1[v] && s2[v])) return false;
		s1[x] += s1[v]; s2[x] += s2[v];
	}
	return true;
}

int main()
{
	n = read(); m = read(); q = read();
	for(int i = 1 , u , v; i <= m ; ++i) u = read() , v = read() , add(u , v) , add(v , u);
	for(int i = 1 ; i <= n ; ++i) if(!dfn[i]) Tarjan(i , -1);
	for(int i = 1 ; i <= n ; ++i) if(!col[i]) col_id++ , dfs1(i);
	for(int i = 1 ; i <= n ; ++i) for(int j = head[i] ; j ; j = e[j].nex) if(col[i] < col[e[j].v]) G[col[i]].push_back(col[e[j].v]) , G[col[e[j].v]].push_back(col[i]);
	for(int i = 1 ; i <= col_id ; ++i) if(!tag[i]) tag_id++ , d[i] = 1 , dfs2(i);
	for(int i = 1 , u , v ; i <= q ; ++i)
	{
		u = read(); v = read(); u = col[u]; v = col[v]; if(u == v) continue;
		if(tag[u] != tag[v]) return puts("No") , 0;
		int p = LCA(u , v);
		s1[u]++; s1[p]--; s2[v]++; s2[p]--;
	}
	for(int i = 1 ; i <= col_id ; ++i) if(d[i] == 1 && !check(i)) return puts("No") , 0;
	puts("Yes");
	return 0;	
}