# CSU 1526 Beam me out! 强连通

```#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];
Edge E = { u, v, head[u], false };
edge[edgenum] = E;
}

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]++;
}
}
bool vis[N];
void bfs(){
memset(vis, 0, sizeof vis);
queue<int> q; q.push(Belong[1]);
vis[Belong[1]] = true;
siz = 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){
}
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){
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;
}
/*
3
2
1
3

*/```

## CSUOJ 1526 Beam me out!

Beam me out! King Remark, first of his name, is a benign ruler and every wrongdoer gets a second chance after repenting his crimes in the Great Maze! Today’s delinquent is a renowned computer scientist, but his fame didn’t do him any good after he de

## CSU 1617: Itself is Itself（强连通缩点）思想转换到图论

1617: Itself is Itself Time Limit: 6 Sec  Memory Limit: 128 MB Submit: 21  Solved: 4 [Submit][Status][Web Board] Description Zuosige always has bad luck. Recently, he is in hospital because of pneumonia. While he is taking his injection, he feels ext

## CSU 1804: 有向无环图（拓扑排序）

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1804 题意:…… 思路:对于某条路径,在遍历到某个点的时候,之前遍历过的点都可以到达它,因此在这个时候对答案的贡献就是∑(a1 + a2 + a3 + ... + ai) * bv,其中a是之前遍历到的点,v是当前遍历的点. 这样想之后就很简单了.类似于前缀和,每次遍历到一个v点,就把a[u]加给a[v],然后像平时的拓扑排序做就行了. 1 #include <bits/stdc++.h>

## Kosaraju算法解析: 求解图的强连通分量

1. 定义 连通分量:在无向图中,即为连通子图. 上图中,总共有四个连通分量.顶点A.B.C.D构成了一个连通分量,顶点E构成了一个连通分量,顶点F,G和H,I分别构成了两个连通分量. 强连通分量:有向图中,尽可能多的若干顶点组成的子图中,这些顶点都是相互可到达的,则这些顶点成为一个强连通分量. 上图中有三个强连通分量,分别是a.b.e以及f.g和c.d.h. 2. 连通分量的求解方法 对于一个无向图的连通分量,从连通分量的任意一个顶点开始,进行一次DFS,一定能遍历这个连通分量的所有顶点.所以

## CSU 1111: 三家人【有趣的思维题】

1111: 三家人 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 2241  Solved: 874 [Submit][Status][Web Board] Description 有三户人家共拥有一座花园,每户人家的太太均需帮忙整理花园.A 太太工作了5 天,B 太太则工作了4 天,才将花园整理完毕.C 太太因为正身怀六甲无法加入她们的行列,便出了90元.请问这笔钱如何分给A.B 二位太太较为恰当?A 应得多少元?90/(5+4)*5=\$50