题意:
给定一个有向图.
求一个最大的集合,是所有属于这个集合的点都满足以下条件:
1.出度不为0
2.指向的点都在这个集合内
3.有属于这个集合的点指向这个点
题解:
我的做法是:对图缩点后,枚举每个点,以这个点作起点,并且这个点是由大于等于2个点缩点而得到的,然后这个点为根,以他能访问到的点构成树,如果所有叶子都是大于等于两个点以上缩点得到的,则说明该树构成一个合法的集合.取最大的合法集合即可.
/* * File: main.cpp * Author: swordholy * * Created on 2011年3月6日, 下午1:27 */ #include <cstdlib> #include <iostream> #include <memory.h> #include <stdio.h> #include<iostream> #include<vector> using namespace std; #define MY_MAX 100004 bool visited[MY_MAX], instack[MY_MAX]; int stack[MY_MAX], top; int N, M; vector<int> graph[MY_MAX]; vector<int> g[MY_MAX]; //rebuilded int dfn[MY_MAX], low[MY_MAX]; int color[MY_MAX], colorn[MY_MAX]; int INDEX, num, en; struct edge { int x, y; }; edge e[MY_MAX]; int min(int x, int y) { if (x < y) return x; else return y; } void tarjan(int u) { int v; dfn[u] = low[u] = INDEX++; stack[++top] = u; instack[u] = true; visited[u] = true; for (size_t i = 0; i < graph[u].size(); ++i) { v = graph[u][i]; if (!visited[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (instack[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { ++num; color[u] = num; do { v = stack[top--]; color[v] = num; instack[v] = false; } while (v != u); } } int d[100005]; int dfs(int x) { int i, j, sum; if (d[x] != -1) return d[x]; d[x] = 0; if ((g[x].size() == 0)) { if (colorn[x] >= 2) {d[x]=colorn[x];return colorn[x];} else return 0; } sum = colorn[x]; for (i = 0; i < g[x].size(); i++) { int temp = dfs(g[x][i]); if (temp == 0) return 0; sum += temp; } d[x] = sum; return sum; } /* */ int main(int argc, char** argv) { int n, i, j, t, u, m, vv, id, idn, v[5]; cin >> t; for (u = 1; u <= t; u++) { scanf("%d %d", &n, &m); for (i = 1; i <= n; i++) graph[i].clear(); en = 0; for (vv = 1; vv <= m; vv++) { scanf("%d %d", &id, &idn); for (i = 1; i <= idn; i++) { scanf("%d", &v[i]); graph[id].push_back(v[i]); ++en; e[en].x = id; e[en].y = v[i]; } } /* for(i=1;i<=5;i++) { for(j=0;j<graph[i].size();j++) printf("%d ",graph[i][j]); printf("/n"); }*/ /// //init.... top = 0; num = 0; INDEX = 1; memset(visited, 0, sizeof (visited)); memset(instack, 0, sizeof (instack)); // //calc color by tarjan for (i = 1; i <= n; i++) if (!visited[i]) tarjan(i); // //rebuild a map for (i = 1; i <= n; i++) g[i].clear(); for (i = 1; i <= en; i++) if (color[e[i].x] != color[e[i].y]) //不能自己指向自己 g[color[e[i].x]].push_back(color[e[i].y]); /// memset(colorn, 0, sizeof (colorn)); for (i = 1; i <= n; i++) colorn[color[i]]++; bool fl = true; memset(d, -1, sizeof (d)); int ans = 0; for (i = 1; i <= num; i++) if (colorn[i] >= 2) { int v = dfs(i); if (v > ans) ans = v; } printf("%d/n", ans); } return 0; }
