Educational Codeforces Round 10 E - Pursuit For Artifacts (强联通缩点 + 回溯)

题目链接：http://codeforces.com/contest/652/problem/E

给你n个点m个边，x和y双向连接，要是z是1表示这条边上有宝藏，0则没有，最后给你起点和终点，问你要是到从起点到终点要是中间遇到宝藏就输出YES，否则就输出NO。

每条边只能经过一次，而且这个图保证连通的。

我用tarjan强连通缩点，把这个图变成一棵树，要是起点终点在一个连通分量里且分量里的边有宝藏，那么就输出YES。否则，就找起点到终点直接的路有没有宝藏，因为缩点之后是一棵树，所以起点和终点只有一条路。那我从起点dfs一遍，par[i]记录的是i前驱节点。那我之后就从终点反向遍历这条路，要是路上有宝藏，就输出YES。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <set>

 using namespace std;

 const int MAXN = 3e5 + ;

 typedef pair <int , int> P;

 struct data {

     int next , to , art;

 }edge[MAXN * ];

 int head[MAXN] , low[MAXN] , dfn[MAXN] , st[MAXN] , block[MAXN] , p[MAXN];

 int top , ord , sccnum , end_point , cont;

 bool instack[MAXN] , vis[MAXN] , ok , res;

 vector <P> G[MAXN];

 void init() {

     memset(head , - , sizeof(head));

 }

 inline void add(int u , int v , int art) {

     edge[cont].next = head[u];

     edge[cont].to = v;

     edge[cont].art = art;

     head[u] = cont++;

 }

 void tarjan(int u , int par) {

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

     st[++top] = u;

     instack[u] = true;

     for(int i = head[u] ; ~i ; i = edge[i].next) {

         int v = edge[i].to;

         if(v == par)

             continue;

         if(!dfn[v]) {

             tarjan(v , u);

             low[u] = min(low[v] , low[u]);

         }

         else if(instack[v]) {

             low[u] = min(low[u] , dfn[v]);

         }

     }

     if(dfn[u] == low[u]) {

         sccnum++;

         int v;

         do {

             v = st[top--];

             instack[v] = false;

             block[v] = sccnum;

         }while(u != v);

     }

 }

 void dfs(int u , int par) {

     p[u] = par;

     for(int i =  ; i < G[u].size() ; i++) {

         int v = G[u][i].first;

         if(par == v)

             continue;

         if(G[u][i].second)

             vis[v] = true;

         dfs(v , u);

     }

 }

 int main()

 {

     int n , m , u , v , art , s , e , heheda = ;

     scanf("%d %d" , &n , &m);

     init();

     for(int i =  ; i < m ; i++) {

         scanf("%d %d %d" , &u , &v , &art);

         add(u , v , art);

         add(v , u , art);

         if(art == )

             heheda = ;

     }

     scanf("%d %d" , &s , &e);

     if(heheda) {

         printf("NO\n");

         return ;

     }

     tarjan( , -);

     end_point = block[e];

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

         for(int i = head[u] ; ~i ; i = edge[i].next) {

             int v = edge[i].to;

             if(block[u] != block[v]) {

                 G[block[u]].push_back(P(block[v] , edge[i].art));

             }

             else {

                 if(!vis[block[u]])

                     vis[block[u]] = (bool)(edge[i].art);

             }

         }

     }

     if(block[s] == end_point && vis[block[s]]) {

         printf("YES\n");

         return ;

     }

     if(vis[block[s]])

         res = true;

     dfs(block[s] , -);

     for(int i = end_point ; ~i ; i = p[i]) {

         if(vis[i])

             res = true;

     }

     if(res)

         printf("YES\n");

     else

         printf("NO\n");

 }

巴特西

Educational Codeforces Round 10 E - Pursuit For Artifacts (强联通缩点 + 回溯)

最新文章

热门文章