POJ 2553 The Bottom of a Graph(강연통 컴포넌트)
POJ 2553 The Bottom of a Graph
제목 링크
제목: 유방향도를 정하고 0의 강연통 분량을 구한다.
사고방식: 줄여서 하면 된다
코드:#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int N = 5005;
int n, m;
vector<int> g[N], save[N];
stack<int> S;
int pre[N], dfn[N], dfs_clock, sccno[N], sccn;
void dfs_scc(int u) {
pre[u] = dfn[u] = ++dfs_clock;
S.push(u);
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (!pre[v]) {
dfs_scc(v);
dfn[u] = min(dfn[u], dfn[v]);
} else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]);
}
if (dfn[u] == pre[u]) {
sccn++;
save[sccn].clear();
while (1) {
int x = S.top(); S.pop();
save[sccn].push_back(x);
sccno[x] = sccn;
if (x == u) break;
}
}
}
void find_scc() {
dfs_clock = sccn = 0;
memset(pre, 0, sizeof(pre));
memset(sccno, 0, sizeof(sccno));
for (int i = 1; i <= n; i++)
if (!pre[i]) dfs_scc(i);
}
int out[N];
int ans[N], an;
int main() {
while (~scanf("%d", &n) && n) {
for (int i = 1; i <= n; i++) g[i].clear();
scanf("%d", &m);
int u, v;
while (m--) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
}
find_scc();
memset(out, 0, sizeof(out));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < g[i].size(); j++) {
int v = g[i][j];
if (sccno[i] != sccno[v]) {
out[sccno[i]]++;
}
}
}
an = 0;
for (int i = 1; i <= sccn; i++) {
if (!out[i]) {
for (int j = 0; j < save[i].size(); j++)
ans[an++] = save[i][j];
}
}
sort(ans, ans + an);
for (int i = 0; i < an; i++)
printf("%d%c", ans[i], i == an - 1 ? '
' : ' ');
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int N = 5005;
int n, m;
vector<int> g[N], save[N];
stack<int> S;
int pre[N], dfn[N], dfs_clock, sccno[N], sccn;
void dfs_scc(int u) {
pre[u] = dfn[u] = ++dfs_clock;
S.push(u);
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (!pre[v]) {
dfs_scc(v);
dfn[u] = min(dfn[u], dfn[v]);
} else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]);
}
if (dfn[u] == pre[u]) {
sccn++;
save[sccn].clear();
while (1) {
int x = S.top(); S.pop();
save[sccn].push_back(x);
sccno[x] = sccn;
if (x == u) break;
}
}
}
void find_scc() {
dfs_clock = sccn = 0;
memset(pre, 0, sizeof(pre));
memset(sccno, 0, sizeof(sccno));
for (int i = 1; i <= n; i++)
if (!pre[i]) dfs_scc(i);
}
int out[N];
int ans[N], an;
int main() {
while (~scanf("%d", &n) && n) {
for (int i = 1; i <= n; i++) g[i].clear();
scanf("%d", &m);
int u, v;
while (m--) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
}
find_scc();
memset(out, 0, sizeof(out));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < g[i].size(); j++) {
int v = g[i][j];
if (sccno[i] != sccno[v]) {
out[sccno[i]]++;
}
}
}
an = 0;
for (int i = 1; i <= sccn; i++) {
if (!out[i]) {
for (int j = 0; j < save[i].size(); j++)
ans[an++] = save[i][j];
}
}
sort(ans, ans + an);
for (int i = 0; i < an; i++)
printf("%d%c", ans[i], i == an - 1 ? '
' : ' ');
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.