\(\mathcal{Description}\)

给定 \(n\) 个点 \(m\) 条边的无向图，判断是否有给每条边定向的方案，使得 \(q\) 组有序点对 \((s,t)\) 都有 \(s\) 可达 \(t\)。

\(n,m,q\le2\times10^5\)。

\(\mathcal{Solution}\)

首先，对于原图中的边双，显然是可以让它们互相可达的，考虑把边双缩点。

此后，图变成了一片森林。单独考虑一棵树，从 \(s\) 到 \(t\) 的有向路径相当于规定了某些点连向父亲的边的方向。所以树上差分，在根上记录点对进入 / 走出子树的次数。若某个棵子树既有进入又有走出就肯定不合法啦。

\(\mathcal{Code}\)

#include <cstdio>

#include <cstdlib>

#include <assert.h>

#define adj( g, u, v ) \

	for ( int i = g.head[u], v; v = g.to[i], i; i = g.nxt[i] )

#define NO() ( puts ( "NO" ), exit ( 0 ) )

const int MAXN = 2e5;

int n, m, q;

int dfc, dfn[MAXN + 5], low[MAXN + 5];

int cnt, bel[MAXN + 5], part, color[MAXN + 5];

int dep[MAXN + 5], fa[MAXN + 5][20], in[MAXN + 5], out[MAXN + 5];

bool cut[MAXN + 5], vis[MAXN + 5], chk[MAXN + 5];

struct Graph {

	int ecnt, head[MAXN + 5], to[MAXN * 2 + 5], nxt[MAXN * 2 + 5];

	Graph (): ecnt ( 1 ) {}

	inline void link ( const int s, const int t ) {

		to[++ ecnt] = t, nxt[ecnt] = head[s];

		head[s] = ecnt;

	}

} G, T;

inline void chkmin ( int& a, const int b ) { if ( b < a ) a = b; }

inline int rint () {

	int x = 0; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () );

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x;

}

inline void Tarjan ( const int u, const int id ) {

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

	adj ( G, u, v ) {

		if ( ! dfn[v] ) {

			Tarjan ( v, i ), chkmin ( low[u], low[v] );

			if ( low[v] > dfn[u] ) cut[i >> 1] = true;

		} else if ( i ^ id ^ 1 ) chkmin ( low[u], dfn[v] );

	}

}

inline void mark ( const int u, const int col ) {

	bel[u] = col, vis[u] = true;

	adj ( G, u, v ) {

		if ( ! cut[i >> 1] && ! vis[v] ) {

			mark ( v, col );

		}

	}

}

inline void init ( const int u, const int f, const int c ) {

	color[u] = c, dep[u] = dep[fa[u][0] = f] + 1;

	for ( int i = 1; fa[u][i - 1]; ++ i ) fa[u][i] = fa[fa[u][i - 1]][i - 1];

	adj ( T, u, v ) if ( v ^ f ) init ( v, u, c );

}

inline int calcLCA ( int u, int v ) {

	assert ( color[u] == color[v] );

	if ( dep[u] < dep[v] ) u ^= v ^= u ^= v;

	for ( int i = 17; ~ i; -- i ) if ( dep[fa[u][i]] >= dep[v] ) u = fa[u][i];

	if ( u == v ) return u;

	for ( int i = 17; ~ i; -- i ) if ( fa[u][i] ^ fa[v][i] ) u = fa[u][i], v = fa[v][i];

	return fa[u][0];

}

inline void check ( const int u, const int f ) {

	chk[u] = true;

	adj ( T, u, v ) if ( v ^ f ) {

		check ( v, u );

		if ( in[v] && out[v] ) NO ();

		in[u] += in[v], out[u] += out[v];

	}

}

int main () {

	n = rint (), m = rint (), q = rint ();

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

		u = rint (), v = rint ();

		G.link ( u, v ), G.link ( v, u );

	}

	for ( int i = 1; i <= n; ++ i ) if ( ! dfn[i] ) Tarjan ( i, -1 );

	for ( int i = 1; i <= n; ++ i ) if ( ! vis[i] ) mark ( i, ++ cnt );

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

		adj ( G, u, v ) if ( cut[i >> 1] ) {

			T.link ( bel[u], bel[v] );

		}

	}

	for ( int i = 1; i <= cnt; ++ i ) if ( ! color[i] ) init ( i, 0, ++ part );

	for ( int i = 1, s, t; i <= q; ++ i ) {

		s = bel[rint ()], t = bel[rint ()];

		if ( s == t ) continue;

		if ( color[s] ^ color[t] ) NO ();

		int w = calcLCA ( s, t );

		++ out[s], -- out[w], ++ in[t], -- in[w];

	}

	for ( int i = 1; i <= n; ++ i ) if ( ! chk[i] ) check ( i, 0 );

	puts ( "YES" );

	return 0;

}

巴特西

Solution -「CF 555E」Case of Computer Network

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章