图关节点求法 c++.txt

图关节点求法的c++实现

#include <iostream> 
#include <fstream> 
#include <string> 
#include <deque> 
using namespace std; 
ifstream fin("fin.in"); 
#define nnode 1000 
deque<int> node[nnode]; 
int n; 
void readin(){ 
    int m; 
    fin>>n; 
    int i,j;     
    for(i=0;i<n;i++){ 
        fin>>m; 
        node.resize(m); 
        for(j=0;j<m;j++){ 
            fin>>node[j]; 
        } 
    } 
} 
deque<int> visited,low,is; 
int min(int a,int b){ 
    if(a>b) return b; 
    return a; 
} 
void foo(){ 
    visited.resize(nnode,0); 
    is.resize(nnode,0); 
    low.resize(nnode,-1); 
    
    int cur,i; 
    deque<int> stack;   
    int ct=1; 
    stack.push_front(0); 
    visited[0]=ct++;         
    while(stack.size()!=0){ 
        cur=stack[0];       
        stack.pop_front(); 
        if(low[cur]==-2){ 
            low[cur]=visited[cur]; 
            for(i=0;i<node[cur].size();i++){ 
                if(visited[node[cur]]<visited[cur]) 
                    low[cur]=min(low[cur],visited[node[cur]]); 
                else{ 
                    if(low[node[cur]]>=visited[cur]) is[cur]=1; 
                    low[cur]=min(low[cur],low[node[cur]]); 
                } 
            }           
            continue; 
        } 
        if(low[cur]!=-1) continue; 
        low[cur]=-2; 
        stack.push_front(cur); 
        for(i=0;i<node[cur].size();i++){ 
            int temp; 
            temp=node[cur]; 
            if(visited[temp]!=0) continue; 
            stack.push_front(temp); 
            visited[temp]=ct++;         
        } 
    } 
} 
    
int main(){ 
    readin(); 
    foo(); 
    for(int i=0;i<n;i++){ 
        cout<<low<<" "; 
    } 
    cout<<endl; 
    for(i=0;i<n;i++){ 
        if(is==1) cout<<i<<" "; 
    } 
    cout<<endl; 
    return 0; 
}