# 挑战程序竞赛系列（75）：4.3强连通分量分解（2）

## 挑战程序竞赛系列（75）：4.3强连通分量分解（2）

```import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main{

String INPUT = "./data/judge/201709/P3180.txt";

public static void main(String[] args) throws IOException {
new Main().run();
}

static final int MAX_N = 10000 + 16;
List<Edge>[] g, rg;
List<Integer> po;
boolean[] used;
int[] cmp;
int V;

class Edge{
int from;
int to;
Edge(int from, int to){
this.from = from;
this.to   = to;
}
}

void init(int V) {
this.V = V;
g    = new ArrayList[MAX_N];
rg   = new ArrayList[MAX_N];
po   = new ArrayList<Integer>();
used = new boolean[MAX_N];
cmp  = new int[MAX_N];
Arrays.fill(used, false);
for (int i = 0; i < V; ++i) g[i]  = new ArrayList<Edge>();
for (int i = 0; i < V; ++i) rg[i] = new ArrayList<Edge>();
}

void add(int from, int to) {
}

void dfs(int v) {
used[v] = true;
for (Edge e : g[v]) {
if (!used[e.to]) dfs(e.to);
}
}

void rdfs(int v, int k) {
used[v] = true;
cmp[v]  = k;
for (Edge e : rg[v]) {
if (!used[e.to]) rdfs(e.to, k);
}
}

int kosarajuSCC() {
for (int i = 0; i < V; ++i) {
if (!used[i]) dfs(i);
}
Arrays.fill(used, false);
int k = 0;
for (int i = po.size() - 1; i >= 0; --i) {
if (!used[po.get(i)]) rdfs(po.get(i), k++);
}
return k;
}

int N = ni();
int M = ni();
init(N);
for (int i = 0; i < M; ++i) {
int from = ni();
int to   = ni();
from --;
to   --;
}
int scc = kosarajuSCC();
int[] count = new int[scc + 1];
for (int i = 0; i < V; ++i) {
count[cmp[i]]++;
}
int ans = 0;
for (int i = 0; i <= scc; ++i) {
if (count[i] >= 2) ans ++;
}
out.println(ans);
}

FastScanner in;
PrintWriter out;

void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}

InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}

public boolean more(){
return in.hasNext();
}

public int ni(){
return in.nextInt();
}

public long nl(){
return in.nextLong();
}

public double nd(){
return in.nextDouble();
}

public String ns(){
return in.nextString();
}

public char nc(){
return in.nextChar();
}

class FastScanner {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}

String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}

public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}

public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}

public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}

public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}

public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}```

0 条评论

• ### 挑战程序竞赛系列（76）：4.3强连通分量分解（3）

挑战程序竞赛系列（76）：4.3强连通分量分解（3） 传送门：POJ 1236: Network of Schools 题意： 校园网：给定N所学校和网络，目...

• ### POJ 刷题系列：1068. Parencodings

题意： 给出一组P-Sequence，每个数代表当前右括号之前的所有左括号数，求W-Sequence，表示当前右括号与它对应的左括号之间的左括号数。还是看例子...

• ### 4.6树上的分治法（3）

在POJ: 1741的计数函数上加个循环，只需将“不超过k”改为“不超过k减去小于k”，就可以得到“等于k”的数量了。

• ### 挑战程序竞赛系列（76）：4.3强连通分量分解（3）

挑战程序竞赛系列（76）：4.3强连通分量分解（3） 传送门：POJ 1236: Network of Schools 题意： 校园网：给定N所学校和网络，目...

• ### poj3264

Description 在每天挤奶的时候，农民约翰的N头牛（1≤n≤50000）总是排成一列。有一天，约翰决定与他的牛们一起玩一个极限飞盘游戏。为了简单起见，他...

• ### 套接字选项

选项影响套接字操作，如 封包路由，OOB数据传输，获取和设置套接字选项分别是 getsockopt  setsockopt 用法如下： int getsocko...

• ### 数据结构与算法-快速排序算法

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 4.7后缀数组

第一次接触后缀数组，采用《挑战》P378的后缀算法，时间复杂度为O(nlog2n)O(n\log^2n)，基本思想如下：

• ### 1062. 昂贵的聘礼

思路： 实际上是一个图模型，采用递归，物品之间的交换有一条关系边，比如国王需要物品2，那么可以用8000来交换，此时子问题就变成了从物品2出发，所需要的最少...