(SCC基于深度优先搜索DFS的强连通分量检索 C++实现) Coursera 斯坦福大学 算法课程 Programming Assignment #5

    #include <iostream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <regex>
    
    using namespace std;
    class vertex{
    private:
    public:
    int leader;
    bool visited;
    int vertexName;
    int finishTime;
    vector<int> edges;
    void push_back(int i){
        edges.push_back(i);
    }
    };
    
    vector<int> finishList;
    
    void readTxt(string file, vector<vertex>& fwdGraph, vector<vertex>& revGraph)
    {
    vector<int> temp_line;
    string line;
    ifstream in(file);
    regex pat_regex("[[:digit:]]+");
    int count = 0;
    while(getline(in, line)) {
        count++;
        for (sregex_iterator it(line.begin(), line.end(), pat_regex), end_it; it != end_it; ++it) {
            temp_line.push_back(stoi(it->str()));
        }
        fwdGraph[temp_line[0] - 1].push_back(temp_line[1] - 1);
        revGraph[temp_line[1] - 1].push_back(temp_line[0] - 1);
        temp_line.clear();
    }
    }
    
    int currentFinishTime = 0;
    int currentLeader = 0;
    
    void DFS(vector<vertex>& fwdGraph, vector<vertex>& revGraph, int i){
    revGraph[i].visited = true;
    revGraph[i].leader = currentLeader;
    for(int j = 0; j < revGraph[i].edges.size(); j++){
        if(revGraph[revGraph[i].edges[j]].visited == false){
            DFS(fwdGraph ,revGraph, revGraph[i].edges[j]);
        }
    }
    finishList[currentFinishTime] = i;
    
    currentFinishTime++;
    }
    
    void DFSLOOP(vector<vertex>& fwdGraph, vector<vertex>& revGraph){
    for(int i = revGraph.size() - 1; i >= 0; i--){
        if(revGraph[i].visited == false){
            currentLeader = i;
            DFS(fwdGraph, revGraph, i);
        }
    }
    }
    
    void DFS2(vector<vertex>& fwdGraph, int i){
    fwdGraph[i].visited = true;
    fwdGraph[i].leader = currentLeader;
    
    for(int j = 0; j < fwdGraph[i].edges.size(); j++){
        if(fwdGraph[fwdGraph[i].edges[j]].visited == false){
            DFS2(fwdGraph, fwdGraph[i].edges[j]);
        }
    }
    }
    
    void DFSLOOP2(vector<vertex>& fwdGraph){
    for(int j = finishList.size() - 1; j >= 0; j--){
        if(fwdGraph[finishList[j]].visited == false){
            currentLeader = finishList[j];
            DFS2(fwdGraph, finishList[j]);
        }
    }
    }
    
    void KosarajuTwoPass(vector<vertex>& fwdGraph, vector<vertex>& revGraph){
    currentFinishTime = 0;
    currentLeader = 0;
    DFSLOOP(fwdGraph, revGraph);
    
    currentFinishTime = 0;
    currentLeader = 0;
    DFSLOOP2(fwdGraph);
    }
    
    int main(){
    vector<vertex> fwdGraph;
    vector<vertex> revGraph;
    finishList.resize(875714);//875714
    fwdGraph.resize(875714);//875714
    revGraph.resize(875714);//875714
    readTxt("../num.txt", fwdGraph, revGraph);// Make sure the right path
    cout<<"finish read, fwd: "<<fwdGraph[0].edges.size()<<" rev: "<<revGraph[0].edges.size()<<endl;
    KosarajuTwoPass(fwdGraph, revGraph);
    
    vector<int> histogram;
    histogram.resize(875714);//875714
    
    for(int i = 0; i < fwdGraph.size(); i++){
        histogram[fwdGraph[i].leader]++;
    }
    
    vector<int> maxSCCnum;
    for(int i = 0; i < 5; i++){
        std::vector<int>::iterator biggest = std::max_element(std::begin(histogram), std::end(histogram));
        maxSCCnum.push_back(*biggest);
        cout<<*biggest<<",";
        histogram.erase(biggest);
    }
    
    cout<<"all Finish"<<endl;
    return 0;
    }
    //434821,968,459,313,211
    
    
    cpp
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-07-12/dgecOpkfqF8b6oN0aJmy3AXTQrit.png)