...
代码块 |
---|
#define MAXN 1005 vector<int> G[MAXN]; // 邻接表,G[i]表示i指向的结点 int n; // 结点数 int topsort() { // 计算各个顶点的入度 vector<int> indegree(n); for(int i = 0; i < n; i++) { for(auto &t : G[i]) { indegree[t]++; } } // 入度为0的先入队 queue<int> Q; for(int i = 0; i < n; i++) { if(indegree[i] == 0) { Q.push(i); } } // 拓扑排序 int count = 0; while(!Q.empty()) { int cur = Q.front(); Q.pop(); count++; for(auto &t : G[cur]) { // 邻接点入度减1,如果为0,则入队 indegree[t]--; if(indegree[t] == 0) { Q.push(t); } } } return count; } |
DFS+三色标记法形式:
代码块 |
---|
#define MAXN 1005
vector<int> G[MAXN]; // 邻接表,G[i]表示i指向的结点
int n; // 结点数
int visited[MAXN]; // 访问状态,0:未访问,1:访问中,2:已访问
int count; // 结点计数
bool valid; // 记录是否是合法的DAG,也就是是否存在环
void dfs(int u) {
visited[u] = 1;
for(auto &v : G[u]) {
if(visited[v] == 0) {
dfs(v);
} else if(visited[v] == 1) {
valid = false;
}
}
visited[u] = 2;
count++;
}
int topsort_DFS() {
count = 0;
valid = true;
for(int i = 0; i < n; i++) {
dfs(i);
}
return count;
} |