UVA 315 Network 求割点、套版题

Source

UESTC 2016 Summer Training #13 Div.2

UVA 315

Source

求割点的个数

套一个求割点和桥模板

然后注意一下边的读入

因为每行不确定多少个数字， 所以用getline()

然后用 isalnum() 来判断是数字还是空格

此外注意这里val < 100， 所以可能有两位数 这样就要

	if(i + 1 < sz && isalnum(ss[i+1])){
		v = 10*(ss[i] - '0') + ss[i+1] - '0';
                i++;
        }
        else v = ss[i] - '0';

然后这里是无向边，所以双向读入

复杂度 O(|V| + |E|)

#include 
#include 
#include 
#include 
#include 
using namespace std;


//!!!!!!
//!这个是纯模版题， 查雷同的时候还请^_^, 毕竟输入边， 然后输出割点数的模版⊙﹏⊙‖∣


//!求割点和桥模板：
const int maxn = 1e3 + 8;

int dfn[maxn], low[maxn], head[maxn], visited[maxn];
bool cut[maxn];//点1~n是否是割点
int n, cnt, k, root, nume;//nume桥的个数

struct Edge{
    int to, next;
}edge[maxn*maxn], cutm[maxn*maxn];//cutm是桥

void addedge(int cu,int cv)
{
    edge[cnt].to = cv;
    edge[cnt].next = head[cu];
    head[cu] = cnt++;
}
void tarjan(int u, int fa)
{
    int son = 0;
    visited[u] = 1;
    dfn[u]=low[u] = ++k;
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(visited[v] == 1 && v != fa)
            low[u] = min(low[u], dfn[v]);
        if(visited[v] == 0){
            tarjan(v, u);
            son++;
            low[u] = min(low[u], low[v]);
            if((u == root && son > 1) || (u != root && dfn[u] <= low[v]))
                cut[u] = 1;
//if(dfn[u]<low[v]) cute[++nume]=Edge(u,v);
//!求桥
        }
    }
    visited[u] = 2;
}

inline void init()
{
    memset(head, -1, sizeof head);
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
    memset(visited, 0, sizeof visited);
    memset(cut, 0, sizeof cut);
    cnt = 0;
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    #endif // LOCAL

    string ss;
    int sz, u, v, ans;
    while(scanf("%d", &n)){
        if(n == 0) break;
        init();
//构造边
        getchar();
        while(true){

            getline(cin, ss);
            sz = ss.size();
            if(1 < sz && isalnum(ss[1]))u = 10*(ss[0] - '0') + ss[1] - '0';
            else u = ss[0] - '0';
            if(u == 0) break;

            //n < 100
            for(int i = 2; i < sz; i++){
                if(isalnum(ss[i])){
                    if(i + 1 < sz && isalnum(ss[i+1])){
                        v = 10*(ss[i] - '0') + ss[i+1] - '0';
                        i++;
                    }
                    else v = ss[i] - '0';
                    addedge(u, v);
                    addedge(v, u);
                }
            }
        }
//work
        //cout<<"here"<<endl;
        root = 1;
        tarjan(root, -1);

        ans = 0;
        for(int i = 1; i <= n; i++)
            if(cut[i]) ans++;
        printf("%dn", ans);
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx