양 방향 dfs 강 한 연결 분량 구하 기

1. 임의의 점 을 원점 으로 dfs 를 진행 하고 경과 점 의 시간 스탬프 를 기록 하 며 시간 스탬프 가 점점 증가한다.2. dfs 를 진행 한 후 그림 의 가장자리 방향 을 반대로 합 니 다.시간 스탬프 의 가장 작은 점 을 원점 (바로 위의 원점) 으로 찾 아 dfs 를 진행 합 니 다.이때 그것 이 도달 할 수 있 는 점 집 은 하나의 연결 분량 이다.검색 한 점 을 기록 합 니 다. 3. 검색 하지 않 은 점 에서 시간 스탬프 의 가장 작은 점 을 원점 으로 하고 dfs 를 계속 합 니 다. 검색 결 과 는 상기 4. 모든 점 을 검색 할 때 까지 3 을 계속 반복 합 니 다.이 알고리즘 은 만약 에 어떤 점 이 반대 방향 전에 도착 할 수 있 고 반대 방향 에서 도 도착 할 수 있다 면 이 두 점 이 강 한 연결 이라는 것 을 의미한다.나 는 도전 프로 그래 밍 경기 에 따라 베 낀 템 플 릿 이다.책 에서 말 하 는 것 은 '점 마다 레이 블 을 주 고 dfs 에 따라 레이 블 이 작 아진 다' 는 뜻 이다.이곳 의 레이 블 은 dfs 를 거 친 후에 모든 점 이 vs 용기 에 있 는 위 치 를 말 해 야 합 니 다.매번 에 레이 블 이 비교적 큰 점 에서 검색 을 할 때마다 여기 레이 블 이 비교적 큰 점 은 특정한 연결 분량 나무의 뿌리 노드 일 것 이다.나 는 dfs 에 따라 레이 블 이 커지 는 반대 방법 을 시도 해 보 았 는데, 결 과 는 나의 생각 이 틀 렸 다 는 것 을 증명 했다.여 12

#include
#include
using namespace std;
#define mem(arr,a) memset(arr,a,sizeof(arr))
#define N 10000+10
int v;
vector<int>G[N];
vector<int>rG[N];
vector<int>vs;
bool used[N];
int cmp[N];
int n, m;
void add(int from, int to){
    G[from].push_back(to);
    rG[to].push_back(from);
}
void dfs(int v){
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++){
        if (!used[G[v][i]])dfs(G[v][i]);
    }
    vs.push_back(v);
}
void rdfs(int v, int k){
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); i++){
        if (!used[rG[v][i]])rdfs(rG[v][i], k);
    }
}
int scc(){
    mem(used, 0);
    vs.clear();
    for (int v = 1; v <= n; v++){
        if (!used[v])
            dfs(v);
    }
    mem(used, 0);
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; i--){
        if (!used[vs[i]])
            rdfs(vs[i], k++);
    }
    return k;

}
int main(){

    while (cin >> n >> m){
        if (!n&&!m)break;
        for (int i = 0; i <= n; i++){
            G[i].clear();
            rG[i].clear();
        }
        while (m--){
            int a, b; cin >> a >> b;
            add(a, b);
        }

        if (scc() == 1)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

다음은 틀 렸 다. 나 도 왜 그런 지 생각 하고 있다.

#include
#include
using namespace std;
#define mem(arr,a) memset(arr,a,sizeof(arr))
#define N 10000+10
int v;
vector<int>G[N];
vector<int>rG[N];
vector<int>vs;
bool used[N];
int cmp[N];
int n, m;
void add(int from, int to){
    G[from].push_back(to);
    rG[to].push_back(from);
}
void dfs(int v){
    used[v] = true;
    vs.push_back(v);
    for (int i = 0; i < G[v].size(); i++){
        if (!used[G[v][i]])dfs(G[v][i]);
    }

}
void rdfs(int v, int k){
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); i++){
        if (!used[rG[v][i]])rdfs(rG[v][i], k);
    }
}
int scc(){
    mem(used, 0);
    vs.clear();
    for (int v = 1; v <= n; v++){
        if (!used[v])
            dfs(v);
    }
    mem(used, 0);
    int k = 0;
    for (int i = 0; i < vs.size();i++)
    {
        if (!used[vs[i]])
            rdfs(vs[i], k++);
    }
    return k;

}
int main(){

    while (cin >> n >> m){
        if (!n&&!m)break;
        for (int i = 0; i <= n; i++){
            G[i].clear();
            rG[i].clear();
        }
        while (m--){
            int a, b; cin >> a >> b;
            add(a, b);
        }

        if (scc() == 1)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}