MYF

HDU 3639 Hawk-and-Chicken

Posted on | In | | Visitors

题目链接

HDU 3639

题目类型：强连通分量

题目分析

题目大意

给你一个有向图,如果从u点能到达v点,那么说u是v的粉丝,现在要你按序输出那些粉丝数目最多的点编号.

解析

我们很容易发现，将强连通分量缩点形成一个DAG图，该DAG图中出度为零的点才有可能是粉丝最多的点，那么我们要找出这些出度为零的点究竟有哪些点最多，所以这就需要进行反向DFS，我们将缩点图形成的DAG中的u->v变成新DAG图中的v->u，找出这个新的DAG图中每个点所可以访问的连通分量所含的元素个数之和，将这些连通分量的下标存进st中，然后找出st中每个连通分量所包含的点即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int maxn = 5000+10;
int dfs_clock;
int scc_cnt;
vector<int> G[maxn],mp[maxn],belong[maxn];
int pre[maxn];
int low[maxn];
int sccno[maxn];
stack<int>S;
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]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if (!sccno[v]){
            low[u] = min(low[u], pre[v]);
        }
    }
    if (low[u] == pre[u]) {
        scc_cnt++;
        belong[scc_cnt].clear();
        while (true) {
            int x = S.top(); S.pop();
            sccno[x] = scc_cnt;
            belong[scc_cnt].push_back(x);
            if (x == u) {
                break;
            }
        }
    }
}
void find_scc(int n){
    scc_cnt = dfs_clock = 0;
    memset(sccno, 0, sizeof(sccno));
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i<=n; i++) {
        if (!pre[i]) {
            dfs(i);
        }
    }
}
bool out[maxn],vis[maxn];
int dfs2(int now){ //对缩点后的DAG的图的反图进行DFS
    vis[now] = true;
    int ret = belong[now].size();
    for (int i = 0; i < mp[now].size(); i++) {
        int v = mp[now][i];
        if (!vis[v]) {
            ret += dfs2(v);
        }
    }
    return ret;
}
void work(int n, int m ){
    for (int i =1; i<=n; i++) {
        G[i].clear();
    }
    while (m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        u++, v++;
        G[u].push_back(v);
    }
    find_scc(n);
    
    // 缩点后的DAG的图的反图
    for (int i = 1; i<=scc_cnt; i++)
        mp[i].clear();
    memset(out, false, sizeof(out));
    for (int u = 1; u<= n; u++) {
        for (int i = 0 ; i<G[u].size(); i++) {
            int v = G[u][i];
            int x = sccno[u];
            int y = sccno[v];
            if (x != y) {
                mp[y].push_back(x);
                out[x] = true;
            }
        }
    }
    
    vector<int> st;
    int mx = -1;
    for (int i = 1; i<=scc_cnt; i++) {
        if (!out[i]) {
            memset(vis, false, sizeof(vis));
            int tmp = dfs2(i);
            if (tmp > mx) { //找到票数更多的人
                st.clear();
                st.push_back(i); //下标为i的强连通分量更优
                mx = tmp;
            }
            else if (tmp==mx){  //下标为i的强连通分量符合条件
                st.push_back(i);
            }
        }
    }
    
    printf("%d\n",mx - 1); //去除自己给自己的票
    vector<int> ans;
    for (auto i : st)
        for (auto j : belong[i])
            ans.push_back(j);
    sort(ans.begin(), ans.end()); //将点排序
    
    // Output
    bool first = true;
    for (int i = 0; i<ans.size(); i++) {
        if (first) {
            printf("%d",ans[i]-1);
            first = false;
        }
        else
            printf(" %d",ans[i]-1);
    }
    printf("\n");
}
int main(){
    int T,cas=1;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("Case %d: ",cas++);
        work(n, m);
    }
    return 0;
}