题解 [ABC142F] Pure

2019/09/28 21:57
阅读数 20

题目描述

给定一个 $n$ 个点,$m$ 条边的有向图 $(n \le 1000, m \le 2000)$。

找到一个子图,使得子图里每个点的入度和出度都等于 1。

输出方案。

正解

题目要求即找到一个环,环内的点都只向外连一条边。

手玩发现可以先找到任意一个环,假如环内有连边,就把环缩小,一直缩到环内每个点出度都为 1。

模拟缩环的过程,发现只要找到一个环内的最小环即可。

那么就用 $bfs$ 搜出一颗有向树,第一条返祖边所连的两个点所在的那个最小环即为答案。

找方案的话可以记一下路径上的 preNode (前驱)。

现场用 $dfs$ 也过了,不过后面被 dqk hack 掉了。

$\color{DeepSkyBlue} Code :$

/*
	bfs 找环
*/
#include <bits/stdc++.h>
#define N 1005
#define M 2005

using namespace std;

int n, m;
int dep[N];
int head[N], nex[M], to[M], e;
int stk[N], top;
bool instack[N], vis[N], G[N][N];
vector<int> res;

inline int Rd() {
	int x = 0; char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return x;
}
inline void Ae(int u, int v) {
	nex[++e] = head[u], head[u] = e;
	to[e] = v;
}

void calc(int u, int v) {
	do {
		res.push_back(stk[top]);
	} while(stk[top--] != v);
	int ans = res.size();
	printf("%d\n", ans);
	for(int i = 0; i < ans; ++i) printf("%d\n", res[i]);
	exit(0);
}
void dfs(int u) {
	stk[++top] = u;
	instack[u] = vis[u] = true;
	for(int i = head[u]; i; i = nex[i]) {
		int v = to[i];
		if(vis[v]) {
			if(instack[v]) calc(u, v);
		} else {
			dfs(v);
		}
	}
	instack[u] = false, --top;
	return;
}

int main() {
	n = Rd(), m = Rd();
	for(int i = 1; i <= m; ++i) {
		int u = Rd(), v = Rd();
		G[u][v] = true;
		Ae(u, v);
	}
	
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			if(G[i][j] && G[j][i]) {
				puts("2");
				printf("%d\n%d\n", i, j);
				return 0;
			}	
		}
	}
	for(int i = 1; i <= n; ++i)
		if(!vis[i])
			dfs(i);
	puts("-1");
	return 0;	
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部