UVA - 11504 Dominos 强连通分量 - c++编程基础

TOP

UVA - 11504 Dominos 强连通分量

2015-11-21 01:01:13 来源: 作者: 【大中小】浏览:2次

Tags：UVA 11504 Dominos 连通分量

题意：多米诺骨牌如果有边存在u -> v 说明u倒了v也自动倒了。问最少需要手动推到几个。

如果一些牌属于同一个强连通分量那么任意推倒其中之一就算全部推倒。可以强连通缩点之后推倒的一定是没有入度的牌。

注意这题不能直接判断所有入度为0的点有几个，因为可能存在入度都不为0 但是存在多个强连通分量。比如

n = 6, m = 6

1 -> 2,

2 -> 3,

3 -> 1,

4 -> 5,

5 -> 6,

6 -> 4.

虽然没有入度为0的点但是需要推2次。

#pragma comment(linker, /STACK:10240000,10240000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #define mod 4294967296 #define MAX 0x3f3f3f3f #define lson o<<1, l, m #define rson o<<1|1, m+1, r #define SZ(x) ((int)ans.size()) #define MAKE make_pair #define INFL 0x3f3f3f3f3f3f3f3fLL #define mem(a) memset(a, 0, sizeof(a)) const double pi = acos(-1.0); const double eps = 1e-9; const int N = 100005; const int M = 20005; typedef long long ll; using namespace std; int n, m; vector 
              
                G[N]; int pre[N], low[N], scc[N], dfs_clock, scc_cnt; stack 
               
                 S; int T; void dfs(int u) { pre[u] = low[u] = ++dfs_clock; S.push(u); for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(pre[v] == 0) { dfs(v); low[u] = min(low[u], low[v]); } else if(scc[v] == 0) { low[u] = min(low[u], low[v]); } } if(low[u] == pre[u]) { scc_cnt++; for(;;) { int x = S.top(); S.pop(); scc[x] = scc_cnt; if(x == u) break; } } } void find_scc() { dfs_clock = scc_cnt = 0; mem(scc); mem(pre); for(int i = 0; i < n; i++) { if(pre[i] == 0) dfs(i); } } int vis[N]; int main() { //freopen(in.txt,r,stdin); cin >> T; while(T--) { cin >> n >> m; for(int i = 0; i < n; i++) G[i].clear(); for(int i = 0; i < m; i++) { int x, y; scanf(%d%d, &x, &y); x--, y--; G[x].push_back(y); } find_scc(); mem(vis); for(int u = 0; u < n; u++) { for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(scc[v] != scc[u]) { vis[ scc[v] ]++; } } } int cnt = 0; //cout << scc_cnt << endl; for(int i = 1; i <= scc_cnt; i++) { if(vis[i] == 0) cnt++; } cout << cnt << endl; } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++数据结构单链表(模板类)	下一篇：C++数据结构顺序表的实现(模板类..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: