LADA C++记录

有关struct的简单用法

• typedef 对struct结构体重命名，简化代码
• 加入构造函数，进行初始化（注：这种情况下智能使用构造函数初始化，而不能再使用花括号）

typedef struct vertex{
    int index, lowlink; 
    bool onStack;
    vertex(){
        index = 0;
        lowlink = 0;
        onStack = false;
    }
    vertex(int i, int l, bool oS) {
        index = i;
        lowlink = l;
        onStack = oS;
    }
}vertex;

自制答案

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <sstream>

using namespace std;

int index = 1;
int LeaderNum = 0;
stack<int> S;

typedef struct vertex{
    int index, lowlink;
    bool onStack;
    vertex(){
        index = 0;
        lowlink = 0;
        onStack = false;
    }
    vertex(int i, int l, bool oS) {
        index = i;
        lowlink = l;
        onStack = oS;
    }
}vertex;

void scc(vector< vector<int> > &Adj, vector<vertex> &Vertex, int v){
    Vertex[v].index = index; 
    Vertex[v].lowlink = index;
    index++;
    S.push(v);
    Vertex[v].onStack = true;
    for (int i = 0; i < Adj[v].size(); i++){
        int u = Adj[v][i];
        if (Vertex[u].index == 0){
            scc(Adj, Vertex, u);
            Vertex[v].lowlink = min(Vertex[v].lowlink, Vertex[u].lowlink);
        }
        else if (Vertex[u].onStack == true){
            Vertex[v].lowlink = min(Vertex[v].lowlink, Vertex[u].lowlink);
        }
    }
    
    if (Vertex[v].index == Vertex[v].lowlink){
        while(1){
            int w = S.top();
            S.pop();
            Vertex[w].onStack = false;
            if ( w == v) break;
        }
        LeaderNum++;
    }
}

int main(){
    int n;
    cin >> n;
    vector< vector<int> > Adj(n);
    vector<vertex> Vertex(n);
    int v, temp;
    while( cin >> v ){
        cin >> temp;
        while(temp!=-1){
            Adj[v].push_back(temp);
            cin >> temp;
        }
    }
    for (int i = 0; i < n; i++){
        if ( Vertex[i].index == 0 ){
            scc(Adj, Vertex, i);    
        }
    }
    cout << LeaderNum;
    return 0;
}