CSU 1526 Beam me out! 强连通

题目链接:点击打开链接

题意:

给定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;
}
/*
3
2
1
3

*/
时间: 03-27

CSU 1526 Beam me out! 强连通的相关文章

CSU 1526: Beam me out!

题意:第一问:从1出发,是不是会走进一个点,然后再也到不了n. 第二问:是不是存在一个环,从1出发可以走到. 对于第一问,我们可以先缩点,然后看看是不是只有一个点,出度为0,还有注意这个点包含n 对于第二问,如果访问的点数sum等于缩点以后的点数,那么就是没有环了. 这里需要注意的是,特判自环......wa成狗 #include<cstdio> #include<cstring> #include<algorithm> #include<iostream>

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 1612: Destroy Tunnels 强连通分量 Kosaraju算法

链接 :  http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1612 题意: 给一个矩阵A 大小N*N, B = A^1 + A^2 + A^3 + .... A^n , B中是否存在非0项. 题目可以转化为 N个点 编号为1-n, 对于任意点v,经过一些任意的步长到达u (u为所有点集的任意一个).离散数学里有图的矩阵相关知识 A^k代表了矩阵中从i到j的步长为k的方法数. 题目就是求整个图是否强连通. 学习了 Kosaraju算法 可以轻

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 1580 Outing 强连通+背包

题目链接:点击打开链接 给定n个人,车的载人量m 下面给出a[i]数组 想要邀请i上车,必须先邀请a[i]上车 问:最多能邀请到多少人. 观察得到,这是一个有向图,按照i->a[i]建边后得到的图是类似于树形,但链的尾部是一个简单环. 如下: 5 2 2 3 4 1 4 则我们必须先同时邀请1234,才能邀请5. 所以建立一个反图(即边的方向相反),然后强连通缩点一下,这样就得到了一个森林(多个树的图). 且对于一个树,只有根节点是需要同时邀请的(因为根节点是个环,子节点都是单个点),而子节点是

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,一定能遍历这个连通分量的所有顶点.所以

POJ 2186 Popular Cows 强连通分量模板

题意 强连通分量,找独立的块 强连通分量裸题 #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <iostream> using namespace std; const int maxn = 50005; int n, m; struct Edge { int v, next;

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