传送门:【CodeForces】466E Information Graph
题目分析:2333一遍AC~
看到这题顿时就有思路了。
首先将操作离线,dfs出一颗树(森林),得到所有节点的时间戳,然后因为每次查询都有一个特性,这个询问的文件是已经发送过的,所以我们用邻接表保存文件属于的查询。
这个题目还需要并查集。
按照操作顺序读取保存的操作,遇到操作一就将x合并到y所在的树的树根上。
遇到操作二就扫一遍询问是(假设这是第i个操作二)文件i的所有询问,如果询问的人y不是x的上司(x不在in[y]和ou[y]内或者x和y还没有建立从属关系(属于同一个连通块))则该询问ans = 0,否则ans = 1。
遇到操作三,ans=1输出YES,否则输出NO,反正操作三都在操作二的时候搞定了。
代码如下:
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define REV( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define CLR( a , x ) memset ( a , x , sizeof a ) #define CPY( a , x ) memcpy ( a , x , sizeof a ) const int MAXN = 100005 ; const int MAXE = 200005 ; struct Edge { int v , n ; int idx ; Edge () {} Edge ( int v , int idx , int n ) : v ( v ) , idx ( idx ) , n ( n ) {} } E[MAXE] ; struct Node { int x , y ; int op ; int idx ; } a[MAXN] ; int H[MAXN] , cntE , Q[MAXN] , cntQ ; int in[MAXN] , ou[MAXN] , dfs_clock ; bool vis[MAXN] ; int ans[MAXN] ; int p[MAXN] ; int idx[MAXN] ; int n , m ; void clear () { cntE = 0 ; cntQ = 0 ; dfs_clock = 0 ; CLR ( H , -1 ) ; CLR ( Q , -1 ) ; CLR ( vis , 0 ) ; REP ( i , 0 , MAXN ) p[i] = i ; } void addedge ( int u , int v ) { E[cntE] = Edge ( v , 0 , H[u] ) ; H[u] = cntE ++ ; } void addquery ( int u , int v , int idx ) { E[cntE] = Edge ( v , idx , Q[u] ) ; Q[u] = cntE ++ ; } int find ( int x ) { return p[x] == x ? x : ( p[x] = find ( p[x] ) ) ; } void dfs ( int u ) { in[u] = ++ dfs_clock ; for ( int i = H[u] ; ~i ; i = E[i].n ) dfs ( E[i].v ) ; ou[u] = dfs_clock ; } void solve () { int cnt = 0 ; clear () ; REP ( i , 0 , m ) { scanf ( "%d" , &a[i].op ) ; if ( a[i].op == 1 ) { scanf ( "%d%d" , &a[i].x , &a[i].y ) ; addedge ( a[i].y , a[i].x ) ; vis[a[i].x] = 1 ; } else if ( a[i].op == 2 ) { scanf ( "%d" , &a[i].x ) ; idx[++ cnt] = i ; } else { scanf ( "%d%d" , &a[i].x , &a[i].y ) ; addquery ( idx[a[i].y] , a[i].x , i ) ; } } FOR ( i , 1 , n ) if ( !vis[i] ) dfs ( i ) ; REP ( i , 0 , m ) { if ( a[i].op == 1 ) p[a[i].x] = find ( a[i].y ) ; else if ( a[i].op == 2 ) { int u = a[i].x ; for ( int j = Q[i] ; ~j ; j = E[j].n ) { int v = E[j].v ; if ( find ( u ) == find ( v ) && in[v] <= in[u] && ou[u] <= ou[v] ) ans[E[j].idx] = 1 ; else ans[E[j].idx] = 0 ; } } else printf ( "%s\n" , ans[i] ? "YES" : "NO" ) ; } } int main () { while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ; return 0 ; }