求割点个数
/* gyt Live up to every day */ #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring> #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 4000+10; const ll maxm = 1e7; const int modd = 10000007; const int INF = 1<<30; const db eps = 1e-9; struct Edge{ int u, v, next; }e[maxn*4]; int n, m, cnt,scnt, tot; stack<int>sta; int dfn[maxn], low[maxn], vis[maxn], head[maxn]; int a[maxn], iscut[maxn], father[maxn]; void init() { memset(head, -1, sizeof(head)); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(vis, 0, sizeof(vis)); memset(iscut, 0, sizeof(iscut)); memset(father, 0, sizeof(father)); while(!sta.empty()) sta.pop(); cnt=0; scnt=0; tot=0; } void add(int u, int v) { e[cnt].v=v, e[cnt].next=head[u]; head[u]=cnt++; } void Tarjan(int s, int fa) { int minn, t; father[s]=fa; dfn[s]=low[s]=++tot; vis[s]=2; sta.push(s); for (int i=head[s]; ~i; i=e[i].next) { int t=e[i].v; if (!dfn[t]) { Tarjan(t, s); low[s]=min(low[s], low[t]); } else { if (vis[t]==2) { low[s]=min(low[s], dfn[t]); } } } } void solve() { while(scanf("%d", &n)!=EOF) { if (!n) break; init(); int u, v; while(scanf("%d",&u) && u){ while(getchar()!=' '){ scanf("%d",&v); add(u,v); add(v,u); } } Tarjan(1, 0); int rootson=0; for (int i=2; i<=n; i++) { int k=father[i]; if (k==1) rootson++; else { if (low[i]>=dfn[k]) { iscut[k]=1; } } } if (rootson>1) iscut[1]=1; int ans=0; for (int i=1; i<=n; i++) { if (iscut[i]) ans++; } printf("%d ", ans); } } int main() { int t = 1; //freopen("in.txt", "r", stdin); //scanf("%d", &t); while(t--) solve(); return 0; }
是否联通
/* gyt Live up to every day */ #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring> #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 100000+10; const ll maxm = 1e7; const int modd = 10000007; const int INF = 1<<30; const db eps = 1e-9; struct Edge{ int u, v, next; }e[maxn]; int n, m, cnt,scnt, tot; stack<int>sta; int dfn[maxn], low[maxn], vis[maxn], head[maxn]; void init() { memset(head, -1, sizeof(head)); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(vis, 0, sizeof(vis)); while(!sta.empty()) sta.pop(); cnt=0; scnt=0; tot=0; } void add(int u, int v) { e[cnt].v=v, e[cnt].next=head[u]; head[u]=cnt++; } void Tarjan(int s) { int minn, t; dfn[s]=low[s]=++tot; vis[s]=2; sta.push(s); for (int i=head[s]; ~i; i=e[i].next) { int t=e[i].v; if (!dfn[t]) { Tarjan(t); low[s]=min(low[s], low[t]); } else { if (vis[t]==2) { low[s]=min(low[s], dfn[t]); } } } if (low[s]==dfn[s]) { scnt++; while(!sta.empty()) { int t=sta.top(); sta.pop(); vis[t]=1; if (t==s) break; } } } void solve() { while(scanf("%d%d", &n, &m)!=EOF) { if (!n&&!m) break; init(); for (int i=0; i<m; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); } for (int i=1; i<=n; i++) { if (!dfn[i]) Tarjan(i); } if (scnt==1) puts("Yes"); else puts("No"); } } int main() { int t = 1; //freopen("in.txt", "r", stdin); //scanf("%d", &t); while(t--) solve(); return 0; }
缩点
/* gyt Live up to every day */ #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring> #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 4000+10; const ll maxm = 1e7; const int modd = 10000007; const int INF = 1<<30; const db eps = 1e-9; struct Edge{ int u, v, next; }e[maxn*4]; int n, m, cnt,scnt, tot; stack<int>sta; int dfn[maxn], low[maxn], vis[maxn], head[maxn]; int du[maxn], color[maxn]; int a[maxn], in[maxn]; void init() { memset(head, -1, sizeof(head)); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(vis, 0, sizeof(vis)); memset(du, 0, sizeof(du)); memset(color, 0, sizeof(color)); for (int i=0; i<maxn; i++) in[i]=INF; while(!sta.empty()) sta.pop(); cnt=0; scnt=0; tot=0; } void add(int u, int v) { e[cnt].v=v, e[cnt].next=head[u]; head[u]=cnt++; } void Tarjan(int s) { int minn, t; dfn[s]=low[s]=++tot; vis[s]=2; sta.push(s); for (int i=head[s]; ~i; i=e[i].next) { int t=e[i].v; if (!dfn[t]) { Tarjan(t); low[s]=min(low[s], low[t]); } else { if (vis[t]==2) { low[s]=min(low[s], dfn[t]); } } } if (low[s]==dfn[s]) { scnt++; while(!sta.empty()) { int t=sta.top(); sta.pop(); vis[t]=1; color[t]=scnt; if (t==s) break; } } } void solve() { while(scanf("%d%d", &n, &m)!=EOF) { for (int i=1; i<=n; i++) { scanf("%d", a+i); } init(); for (int i=0; i<m; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); } for (int i=1; i<=n; i++) { if (!dfn[i]) Tarjan(i); } for (int u=1; u<=n; u++) { for (int i=head[u]; ~i; i=e[i].next) { int v=e[i].v; if (color[u]!=color[v]) { du[color[v]]++; } } } int ans=0, ansnum=0; for (int i=1; i<=scnt; i++) { if (!du[i]) { ans++; int num=INF; for (int j=1; j<=n; j++) { if (color[j]==i) { in[i]=min(a[j], in[i]); } } ansnum+=in[i]; } } printf("%d %d ", ans, ansnum); } } int main() { int t = 1; //freopen("in.txt", "r", stdin); //scanf("%d", &t); while(t--) solve(); return 0; }
点联通板子
/* gyt Live up to every day */ #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring> #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 4000+10; const ll maxm = 1e7; const int modd = 10000007; const int INF = 1<<30; const db eps = 1e-9; int cas = 1; int n, m; int head[maxn], cnt, dfn[maxn], low[maxn]; int bcc_cnt, tim, bccno[maxn]; bool iscut[maxn]; vector<int> bcc[maxn]; stack<int> S; struct Edge { int u, v, w, next; } e[maxn*maxn]; void init() { bcc_cnt = cnt = 0; memset(head, -1, sizeof(head)); memset(iscut, 0, sizeof(iscut)); memset(dfn, 0, sizeof(dfn)); } void add(int u, int v, int c) { e[cnt].u = u; e[cnt].v = v; e[cnt].w = c; e[cnt].next = head[u]; head[u] = cnt++; } void tarjan(int u, int fa) { dfn[u] = low[u] = ++tim; int child = 0; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].v; if (!dfn[v]) { S.push(i); child++; tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) { iscut[u] = true; bcc[++bcc_cnt].clear(); while (1) { int tmp = S.top(); S.pop(); bccno[tmp] = bcc_cnt; bcc[bcc_cnt].push_back(tmp); bccno[tmp^1] = bcc_cnt; bcc[bcc_cnt].push_back(tmp^1); if (e[tmp].u == u && e[tmp].v == v) break; } } } else if (dfn[v] < dfn[u] && v != fa) { S.push(i); low[u] = min(low[u], dfn[v]); } } if (fa == -1 && child == 1) iscut[u] = false; } void solve() { int cas = 1; while (scanf("%d", &n)!=EOF) { init(); if (n==0) break; int u, v; while(scanf("%d",&u) && u){ while(getchar()!=' '){ scanf("%d",&v); add(u,v,1); add(v,u,1); } } tarjan(1, -1); int ans=0; for (int i = 1; i <= n; i++) { if (iscut[i]) { ans++; } } cout<<ans<<endl; } } int main() { int t = 1; //freopen("in.txt", "r", stdin); //scanf("%d", &t); while(t--) solve(); return 0; }