题目链接：点击打开链接
题意：
给定n个点的有向图（1为起点，，n为终点）
下面每两行给出一个点的出度和所连接的下一个点。
第n个点是没有出度的
图是这样的： 1->2, 1->3, 2->3
第一问：
若存在一种方案使得这个人进入一个点后再也不能到达终点则输出 PRISON , 否则输出 PARDON
第二问：
若这个人可以在图里走无穷步则输出UNLIMITED, 否则输出LIMITED
#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <map>#include <vector>template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;typedef long long ll;typedef pair<int, int> pii;const int N = 50500;const int inf = 1e8;//N为最大点数const int M = 7500000;//M为最大边数int n;//n m 为点数和边数struct Edge{int from, to, nex;bool sign;//是否为桥}edge[M];int head[N], edgenum;void add(int u, int v){//边的起点和终点Edge E = { u, v, head[u], false };edge[edgenum] = E;head[u] = edgenum++;}int DFN[N], Low[N], Stack[N], top, Time; //Low[u]是点集{u点及以u点为根的子树} 中(所有反向弧)能指向的(离根最近的祖先v) 的DFN[v]值(即v点时间戳)int taj;//连通分支标号，从1开始int Belong[N];//Belong[i] 表示i点属于的连通分支bool Instack[N];vector<int> bcc[N]; //标号从1开始void tarjan(int u, int fa){DFN[u] = Low[u] = ++Time;Stack[top++] = u;Instack[u] = 1;for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].to;if (DFN[v] == -1){tarjan(v, u);Low[u] = min(Low[u], Low[v]);if (DFN[u] < Low[v]){edge[i].sign = 1;//为割桥}}else if (Instack[v]) Low[u] = min(Low[u], DFN[v]);}if (Low[u] == DFN[u]){int now;taj++; bcc[taj].clear();do{now = Stack[–top];Instack[now] = 0;Belong[now] = taj;bcc[taj].push_back(now);} while (now != u);}}void tarjan_init(int all){memset(DFN, -1, sizeof(DFN));memset(Instack, 0, sizeof(Instack));top = Time = taj = 0;for (int i = 1; i <= all; i++)if (DFN[i] == -1)tarjan(i, i); //注意开始点标！！！}vector<int>G[N];int du[N], hehe[N];bool itself[N];void suodian(){memset(du, 0, sizeof(du));for (int i = 1; i <= taj; i++){G[i].clear();hehe[i] = false;for (int j = 0; j < bcc[i].size(); j++)if (itself[bcc[i][j]])hehe[i] = true;}for (int i = 0; i < edgenum; i++){int u = Belong[edge[i].from], v = Belong[edge[i].to];if (u != v)G[u].push_back(v), du[v]++;}}void init(){ memset(head, -1, sizeof(head)); edgenum = 0; }bool vis[N];int siz, bad;void bfs(){memset(vis, 0, sizeof vis);queue<int> q; q.push(Belong[1]);vis[Belong[1]] = true;siz = 0;bad = 0;while (!q.empty()){int u = q.front(); q.pop();//printf(" –%d\n", u);if ((int)bcc[u].size() > 1 || hehe[u])siz++;if ((int)G[u].size() == 0){if (u != Belong[n])bad++;}for (int i = 0; i < G[u].size(); i++){int v = G[u][i];//printf(" **%d\n", v);if (!vis[v]){vis[v] = true;q.push(v);}}}}int main() {while (cin >> n){init();for (int i = 1, num, j; i < n; i++){itself[i] = false;rd(num); while (num–>0){rd(j), add(i, j);if (j == i)itself[i] = true;}}itself[n] = false;tarjan_init(n);suodian();//for(int i = 1; i <= n; i++)printf("%d ", Belong[i]); puts("");bfs();//printf("leaf:%d siz:%d\n", leaf, siz);if (vis[Belong[n]] && bad == 0) printf("PARDON ");else printf("PRISON ");!siz ? puts("LIMITED") : puts("UNLIMITED");}return 0;}/*3213*/
拿望远镜看别人，拿放大镜看自己。
