Editorial for Tìm khớp và cầu (Cơ bản)
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
uses math; var n,m,i,j,cnt,cau,khop:longint; p,low,num,cha,con:array[1..10010] of longint; a,b,c:array[1..100010] of longint; d:array[1..10010] of boolean; procedure visit(x,y:longint); var i:longint; begin inc(cnt); num[x]:=cnt; low[x]:=cnt; cha[x]:=y; for i:=p[x]+1 to p[x+1] do if a[i]<>y then begin if num[a[i]]>0 then low[x]:=min(low[x],num[a[i]]) else begin visit(a[i],x); low[x]:=min(low[x],low[a[i]]); end; end; end; begin read(n,m); for i:=1 to m do begin read(b[i],c[i]); inc(p[b[i]]); inc(p[c[i]]); end; for i:=2 to n+1 do inc(p[i],p[i-1]); for i:=1 to m do begin a[p[b[i]]]:=c[i]; dec(p[b[i]]); a[p[c[i]]]:=b[i]; dec(p[c[i]]); end; for i:=1 to n do if cha[i]=0 then visit(i,-1); for i:=1 to n do if cha[i]>0 then inc(con[cha[i]]); for i:=1 to n do begin j:=cha[i]; if j<0 then continue; if low[i]>=num[i] then inc(cau); if d[j] then continue; if (low[i]>=num[j]) and ((cha[j]<>-1) or (con[j]>1)) then begin d[j]:=true; inc(khop); end; end; writeln(khop,' ',cau); end.
Code mẫu của happyboy99x
#include<cstdio> #include<vector> using namespace std; const int N = 10005; int n, m, cut, bridge, t, d[N], low[N]; vector<vector<int> > g; void enter() { scanf("%d%d",&n,&m); g.resize(n); for(int i = 0; i < m; ++i) { int u, v; scanf("%d%d",&u,&v); g[--u].push_back(--v); g[v].push_back(u); } } void dfs(int u, int p) { low[u] = d[u] = ++t; int iscut = 0, nchild = 0; for(vector<int>::iterator v = g[u].begin(); v != g[u].end(); ++v) if(d[*v] == 0) { ++nchild; dfs(*v, u); low[u] = min(low[u], low[*v]); if(low[*v] >= d[u] && p != -1 || nchild == 2 && p == -1) iscut = 1; if(low[*v] >= d[*v]) ++bridge; } else if(*v != p) low[u] = min(low[u], d[*v]); cut += iscut; } void solve() { for(int u = 0; u < n; ++u) if(d[u] == 0) dfs(u, -1); printf("%d %d\n", cut, bridge); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 10005; const int oo = 123456789; using namespace std; vector<int> a[N]; int par[N], low[N], num[N], nchild[N]; bool cut[N]; int m, n, Time, bridge, art; void DFS(int u) { num[u] = ++Time; low[u] = n+1; int i, v; for(i=0; i<a[u].size(); i++) { v = a[u][i]; if (v == par[u]) continue; if (par[v] == 0) { nchild[u]++; par[v] = u; DFS(v); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], num[v]); } } int main() { scanf("%d %d", &n, &m); int i, u, v; for(i=1; i<=m; i++) { scanf("%d %d", &u, &v); a[u].push_back(v); a[v].push_back(u); } for(i=1; i<=n; i++) if (par[i] == 0) { par[i] = -1; DFS(i); } //bridges for(v=1; v<=n; v++) { u = par[v]; if (u != -1 && low[v] >= num[v]) bridge++; } for(v=1; v<=n; v++) if (par[v] != -1) { u = par[v]; if (low[v] >= num[u]) cut[u] = cut[u] || (par[u] != -1) || (nchild[u] >= 2); } for(i=1; i<=n; i++) if (cut[i]) art++; printf("%d %d", art, bridge); return 0; }
Code mẫu của RR
#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <cmath> #include <vector> #include <cstdlib> #include <set> #include <queue> #include <stack> #include <memory.h> #include <cassert> #include <sstream> #define oo 1000111000 #define PI acos(-1.0) #define FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++) #define FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--) #define REP(i,n) for(int i = 0, _n = (n); i < _n; i++) #define REPD(i,n) for(int i = (n) - 1; i >= 0; i--) #define PB push_back #define MP make_pair #define F first #define S second #define SIZE(c) (c).size() #define RESET(c,x) memset(c,x,sizeof(c)) using namespace std; typedef pair <int, int> PII; typedef long long LL; inline void OPEN(const string &s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } #define MAXV 100000 int V; vector <int> G[MAXV + 5]; int dfs_low[MAXV + 5], dfs_num[MAXV + 5], dfs_parent[MAXV + 5]; int dfsNumberCounter, dfsRoot, rootChildren; bool articulation_vertex[MAXV + 5]; int nBridge, nAp; void articulationPointAndBridge(int u) { dfs_low[u] = dfs_num[u] = dfsNumberCounter++; REP (j, SIZE(G[u])) { int v = G[u][j]; if (dfs_num[v] == -1) { dfs_parent[v] = u; if (u == dfsRoot) rootChildren++; articulationPointAndBridge(v); if (dfs_low[v] >= dfs_num[u]) articulation_vertex[u] = true; if (dfs_low[v] > dfs_num[u]) ++nBridge; dfs_low[u] = min(dfs_low[u], dfs_low[v]); } else if (v != dfs_parent[u]) dfs_low[u] = min(dfs_low[u], dfs_num[v]); } } int main() { scanf("%d", &V); int m; scanf("%d", &m); while (m--) { int u, v; scanf("%d%d", &u, &v); --u; --v; G[u].PB(v); G[v].PB(u); } dfsNumberCounter = 0; RESET(dfs_num, -1); RESET(dfs_low, 0); RESET(dfs_parent, 0); RESET(articulation_vertex, 0); REP (i, V) if (dfs_num[i] == -1) { dfsRoot = i; rootChildren = 0; articulationPointAndBridge(i); articulation_vertex[dfsRoot] = (rootChildren > 1); } REP (i, V) if (articulation_vertex[i]) ++nAp; printf("%d %d\n", nAp, nBridge); return 0; }
Code mẫu của skyvn97
#include<set> #include<cstdio> #include<vector> #include<cstring> #define MAX 10101 using namespace std; typedef pair<int,int> ii; vector<int> g[MAX]; set<ii> bl; int m,n; int low[MAX]; int num[MAX]; int nch[MAX]; bool cutv[MAX]; int cnt; int nb,nc; void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); int i,u,v; for (i=1;i<=n;i=i+1) g[i].clear(); for (i=1;i<=m;i=i+1) { scanf("%d",&u); scanf("%d",&v); g[u].push_back(v); g[v].push_back(u); } } int min(const int &x,const int &y) { if (x<y) return (x); else return (y); } void visit_bridge(const int &u) { int i,v; cnt++; num[u]=cnt; low[u]=n+1; for (i=0;i<g[u].size();i=i+1) { v=g[u][i]; if (bl.find(ii(u,v))!=bl.end()) continue; bl.insert(ii(v,u)); if (num[v]==0) { visit_bridge(v); if (low[v]>num[u]) nb++; low[u]=min(low[u],low[v]); } else low[u]=min(low[u],num[v]); } } void count_bridge(void) { memset(low,0,sizeof low); memset(num,0,sizeof num); bl.clear(); nb=0; cnt=0; int i; for (i=1;i<=n;i=i+1) if (num[i]==0) visit_bridge(i); printf("%d",nb); } void visit_cutvert(const int &u) { int i,v; cnt++; num[u]=cnt; low[u]=n+1; cutv[u]=false; for (i=0;i<g[u].size();i=i+1) { v=g[u][i]; if (num[v]==0) { nch[u]++; visit_cutvert(v); cutv[u]=cutv[u]||(low[v]>=num[u]); low[u]=min(low[u],low[v]); } else low[u]=min(low[u],num[v]); } } void count_cutvert(void) { memset(low,0,sizeof low); memset(num,0,sizeof num); memset(nch,0,sizeof nch); nc=0; cnt=0; int i; for (i=1;i<=n;i=i+1) { if (num[i]==0) { visit_cutvert(i); if (nch[i]<2) cutv[i]=false; } } for (i=1;i<=n;i=i+1) nc+=cutv[i]; printf("%d ",nc); } int main(void) { loadgraph(); count_cutvert(); count_bridge(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> #include <vector> #include <cstdio> #include <set> using namespace std; int n, m; vector<pair<int,int> > ke[10010]; int num[10010], low[10010], fa[10010]; bool mark[10010], vsting[10010], khop[10010]; int tt = 0, sokhop, socau; void dfs(int i, int edge) { vsting[i] = true; mark[i] = true; num[i] = tt++; low[i] = num[i]; int sc = 0; for(int k=0;k<ke[i].size();++k) { int j = ke[i][k].first; if(!mark[j]) { ++sc; fa[j] = i; dfs(j, ke[i][k].second); low[i] = min( low[i], low[j]); } else if(ke[i][k].second != edge && vsting[j]) low[i] = min( low[i], num[j]); } if(edge != -1 && low[i] == num[i]) ++socau; if(edge == -1) { if(sc > 1) khop[i] = true; else khop[i] = false; } if(edge != -1 && low[i] >= num[fa[i]]) khop[fa[i]] = true; vsting[i] = false; } int main() { scanf("%d%d", &n, &m); set<pair<int,int> > se; for(int i=0;i<m;++i) { int u, v; scanf("%d%d", &u, &v); if(!se.count(make_pair(u,v))) { ke[u].push_back(make_pair(v,i)); ke[v].push_back(make_pair(u,i)); se.insert(make_pair(u,v)); se.insert(make_pair(v,u)); } } for(int i=1;i<=n;++i) if(!mark[i]) { dfs(i, -1); } for(int i=1;i<=n;++i) if(khop[i]) ++sokhop; cout << sokhop << " " << socau << endl; return 0; }
Comments