题目大意：有N个人进行投票，想要选择出最受欢迎的人，投票的规则如下 1.不能投给自己 2.投票可以传递，比如A投给B一票，B投给C一票，那么C就得到了A的一票和B的一票
问票数最多能得多少，得到最高票的有哪些人
解题思路：求出所有的强连通分量，这些强连通分量里面的人得到的票数都是一样的，为强连通分量内的点数-1
接着将强连通分量进行缩点，用桥连接起来，反向建边 接着以所有出度为0的点进行dfs，，得出这个连通分量内的点所能得到的最高票数(出度为0的点得到的票数是最多的)
Edge{int to, next;}E[M];struct Node{int x, y;}node[M];int head[N], pre[N], sccno[N], stack[N], lowlink[N], in[N], Sum[N], num[N];int n, m, tot, dfs_clock, scc_cnt, top;bool vis[N];void AddEdge(int u, int v) {E[tot].to = v;E[tot].next = head[u];head[u] = tot++;}void init() {scanf(“%d%d”, &n, &m);memset(head, -1, sizeof(head));tot = 0;for (int i = 0; i < m; i++) {scanf(“%d%d”, &node[i].x, &node[i].y);AddEdge(node[i].x, node[i].y);}}void dfs(int u) {pre[u] = lowlink[u] = ++dfs_clock;stack[++top] = u;int v;for (int i = head[u]; i != -1; i = E[i].next) {v = E[i].to;if (!pre[v]) {dfs(v);lowlink[u] = min(lowlink[u], lowlink[v]);}else if (!sccno[v]) {lowlink[u] = min(lowlink[u], pre[v]);}}if (lowlink[u] == pre[u]) {++scc_cnt;num[scc_cnt] = 0;while (1) {v = stack[top–];sccno[v] = scc_cnt;num[scc_cnt]++;if (v == u)break;}}}int dfs2(int u) {vis[u] = true;int tmp = num[u];for (int i = head[u]; i != -1; i = E[i].next) {int v = E[i].to;if (!vis[v]) {tmp += dfs2(v);}}return tmp;}int cas = 1;void solve() {memset(pre, 0, sizeof(pre));memset(sccno, 0, sizeof(sccno));dfs_clock = scc_cnt = top = 0;for (int i = 0; i < n; i++)if (!pre[i])dfs(i);memset(head, -1, sizeof(head));tot = 0;memset(in, 0, sizeof(in));memset(Sum, 0, sizeof(Sum));int u, v;for (int i = 0; i < m; i++) {u = sccno[node[i].x];v = sccno[node[i].y];if (u != v) {AddEdge(v, u);in[u]++;}}int Max = -1;for (int i = 1; i <= scc_cnt; i++) {if (in[i] == 0) {memset(vis, 0, sizeof(vis));Sum[i] += dfs2(i);Max = max(Sum[i], Max);}}printf(“Case %d: %d\n”, cas++, Max – 1);bool flag = false;for (int i = 0; i < n; i++) {if (Sum[sccno[i]] == Max) {if (flag)printf(” “);printf(“%d”, i);flag = true;}}printf(“\n”);}int main() {int test;scanf(“%d”, &test);while (test–) {init();solve();}return 0;}
你怎么样对待别人被人就怎么样对待你。
