题解 CF1095D 【Circular Dance】

小黑AWM

2018-12-28 23:40:10

Solution

观察可以发现**对于任意一个点,他的直接后继节点肯定是那个和他有共同后继节点的那个节点**所以利用这一条性质我们可以很方便的从任意一个起点出发然后选定他的儿子和孙子,再从孙子找下去,子子孙孙直到返祖(重复)为止。具体实现细节见代码。 ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxn = 2e5 + 10; int n, at; int edge[maxn][2]; int ans[maxn], top, visit[maxn]; int judge(int father, int id){ int son = edge[father][id]; int grandson = edge[father][id^1]; if(edge[son][0] == grandson || edge[son][1] == grandson) return true; return false; } int main(){ while(cin >> n){ top = 0; memset(edge, 0, sizeof(edge)); memset(ans, 0, sizeof(ans)); memset(visit, 0, sizeof(visit)); for(int i = 1; i <= n; i++) cin >> edge[i][0] >> edge[i][1]; ans[++top] = 1; at = 1; visit[at] = true; while(!visit[edge[at][0]] || !visit[edge[at][1]]){ int u = edge[at][0]; int v = edge[at][1]; if(judge(at, 0)){ ans[++top] = u; visit[u] = true; if(!visit[v]) ans[++top] = v, visit[v] = true; }else{ ans[++top] = v; visit[v] = true; if(!visit[u]) ans[++top] = u, visit[u] = true; } at = ans[top]; } for(int i = 1; i <= top; i++) cout << ans[i] << " "; cout << endl; } return 0; } ```