P3465

大概是一道凸轮小水题？ 顺便纪念一下 $pecky$ 神犇 (提供的思路

使每一个点的入度为 $1$ （在只考虑有向边的情况下

然后 只要 有环 就成立 ... 思路这样大概就结束了

代码主要在 :

$1.$ 找环 : 可用并查集 在两点连边时 判断一下是否已经在同一集合中， 如果已经在一个集合中 再连一条边 必然构成一个环 (注意图不连通要找多个环)

for(int i = 1;i <= m;i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v); add(v, u);
		int fx = find(u), fy = find(v);
    	//注意在这里
		if(fx == fy) s[++s[0]] = u; //#4789的点 (多个环 
    
		f[fx] = fy;
	}

$2.\ dfs:\$ 对于每一个连通图， 我们只需要选取其中一个环任意一点作为起点必然能找到一条路径使每个点入度为一 (注意是双向边建图 要判一下不要连成双向边)

void dfs(int u, int ss) {
	for(int i = head[u]; i;i = nxt[i]) {
		int v = to[i]; 
        
        //注意在这里
		if(ans[v] || ans[u] == v/*#5#6的点*/ ) continue;
        
		ans[v] = u;
		if(v == ss) continue;
		dfs(v, ss);
	}
}

$3.$ 也算一个小注意吧 ： 整张图不连通 要保证每个连通图都有环

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, m;
int nxt[maxn << 1], to[maxn << 1], head[maxn], cnt;
void add(int u, int v) {
	to[++cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
}
int f[maxn], s[maxn];
int find(int x) {
	return x == f[x] ? x : find(f[x]);
}
int ans[maxn], p[maxn];
void dfs(int u, int ss) {
	for(int i = head[u]; i;i = nxt[i]) {
		int v = to[i];
		if(ans[v] || ans[u] == v/*#5#6的点*/ ) continue;
		ans[v] = u;
		if(v == ss) continue;
		dfs(v, ss);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i++) f[i] = i;
	for(int i = 1;i <= m;i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v); add(v, u);
		int fx = find(u), fy = find(v);
		if(fx == fy) s[++s[0]] = u; //#4789的点 (多个环 
		f[fx] = fy;
	}
	if(!s) {
		printf("NIE\n");
		return 0;
	}
	for(int i = 1;i <= s[0];i++) 
		if(!ans[s[i]])
			dfs(s[i], s[i]);
    
    //注意在这里
	for(int i = 1;i <= n;i++) {
		if(ans[i] == 0) {
			printf("NIE\n"); //#2#3的点 
			return 0; 
		}
	}
    
	printf("TAK\n");
	for(int i = 1;i <= n;i++) printf("%d\n", ans[i]);
	return 0;
}

#include <bits/stdc++.h> 
using namespace std;
const int N=1e5+10;
vector<int> G[N];
int n,m;
int fa[N],ok,t;
bool vis[N];
void dfs(int x,int xfa,int &t)
{
	vis[x]=1;
	for(int y:G[x])if(y!=xfa)
	{
		int tt=t;
		if(vis[y])
		{
			ok=1;
			if(t==0)t=1;//当前联通块未返祖，否则不管这条边 
		}
		else
		{
			fa[y]=x;
			dfs(y,x,t);
		}
		if(tt!=t)fa[x]=y;//凡是进去前后t不一样的都要把边反向
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i)
	{
		if(!vis[i])//未走过 
		{
			ok=0;t=0;
			dfs(i,0,t);
			if(!ok) {printf("NIE\n"); return 0;} 
		}
	}
	printf("TAK\n");
	for(int i=1;i<=n;++i) printf("%d\n",fa[i]);
	return 0;
}