计科余定成

用户名：dotcpp0598358

访问量：15770

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13043
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

求具有abcd=(ab+cd)2性质的四位数
浏览：73

[NOIP2004]合并果子
浏览：89

家谱(并查集做法）
浏览：76

你可能喜欢

刻录光盘（c++）

　　作者: 计科余定成　　　　发表时间：2023-10-03 18:13:06 浏览：66　|　评论：0　

原题链接：刻录光盘(cdrom)

## 解题思路
求强联通分量，统计入度为0的即可
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;

struct edge {
	int to, ne;
} e[N * 10];
int h[N], idx;
void add(int u, int v) {
	e[++idx].to = v;
	e[idx].ne = h[u];
	h[u] = idx;
}

int dfn[N], low[N], tot;
int scc[N], siz[N], cnt;
stack<int> stk;
bool ins[N];

void tarjan(int u) {
	dfn[u] = low[u] = ++tot;
	stk.push(u), ins[u] = 1;

for (int i = h[u]; i; i = e[i].ne) {
		int v = e[i].to;
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (ins[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}

if (dfn[u] == low[u]) {
		cnt++;
		int v;
		do {
			v = stk.top(), stk.pop(), ins[v] = 0;
			scc[v] = cnt;
			siz[cnt]++;
		} while (v != u);
	}
}

int n, m;
int u, v;
int in[N];
int ans;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		u = i;
		while (cin >> v) {
			if (v == 0) break;
			add(u, v);
		}
	}

for (int i = 1; i <= n; i++) {
		if (!dfn[i]) tarjan(i);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = h[i]; j; j = e[j].ne) {
			int v = e[j].to;
			if (scc[i] != scc[v]) {
				in[scc[v]]++;
			}
		}
	}

for (int i = 1; i <= cnt; i++) {
		if (in[i] == 0) ans++;
	}
	cout << ans;
	return 0;
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C二级辅导-同因查找（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

刻录光盘（c++）

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

兰顿蚂蚁（C++代码）

C语言训练-大、小写问题（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

演讲大赛评分（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

C二级辅导-同因查找 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

刻录光盘（c++）

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

兰顿蚂蚁 （C++代码）

C语言训练-大、小写问题 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

演讲大赛评分 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C二级辅导-同因查找（C语言代码）

　　评论区

兰顿蚂蚁（C++代码）

C语言训练-大、小写问题（C语言代码）

演讲大赛评分（C语言代码）