Editorial for VOI 06 Bài 5 - Mạng máy tính
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
const fi=''; fo=''; maxn=2005; maxm=30005; var n,sm,m,dem,last,re,ri,rj,ne,nf:longint; a:array[1..maxn,1..maxn] of boolean; b:array[1..maxm,0..1] of longint; free,e,f:array[1..maxn] of boolean; low,num,d,st:array[1..maxn] of longint; procedure rf; var i,x,y:longint; begin assign(input,fi); reset(input); readln(n,m); for i:=1 to m do begin readln(b[i,0],b[i,1]); a[b[i,0],b[i,1]]:=true; end; for i:=1 to n do free[i]:=true; close(input); end; function pop:longint; begin pop:=st[last]; dec(last); end; procedure push(i:longint); begin inc(last); st[last]:=i; end; function min(u,v:longint):longint; begin if u<v then min:=u else min:=v; end; procedure visit(x:longint); var i:longint; begin inc(dem); num[x]:=dem; low[x]:=dem; push(x); for i:=1 to n do if free[i] and a[x,i] then if num[i]>0 then low[x]:=min(low[x],num[i]) else begin visit(i); low[x]:=min(low[x],low[i]); end; if num[x]=low[x] then begin inc(sm); d[x]:=sm; repeat i:=pop; free[i]:=false; d[i]:=sm; until i=x; end; end; procedure pr; var i,j,t,u,v:longint; begin for i:=1 to n do if free[i] then visit(i); if sm=1 then begin for i:=1 to n do for j:=1 to n do if (i<>j) and not a[i,j] then begin ri:=i; rj:=j; end; exit; end; for i:=1 to m do begin if d[b[i,0]]=d[b[i,1]] then continue; if not e[d[b[i,0]]] then begin e[d[b[i,0]]]:=true; inc(ne); end; if not f[d[b[i,1]]] then begin f[d[b[i,1]]]:=true; inc(nf); end; end; if (ne=sm-1) and (nf=sm-1) then begin for u:=1 to n do if not e[u] then break; for ri:=1 to n do if d[ri]=u then break; for v:=1 to n do if not f[v] then break; for rj:=1 to n do if d[rj]=v then break; end else re:=1; end; procedure wf; begin assign(output,fo); rewrite(output); if re=1 then writeln('NO') else begin writeln('YES'); writeln(ri,' ',rj); end; close(output); end; begin rf; pr; wf; end.
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 2222; using namespace std; int low[N], num[N], st[N], lab[N], in[N], out[N]; int n, m, cnt, scc, top; bool was[N]; vector<int> a[N]; void DFS(int u) { low[u] = num[u] = ++cnt; st[++top] = u; int i, v; for(i=0; i<a[u].size(); i++) { v = a[u][i]; if (was[v]) continue; if (num[v] != 0) low[u] = min(low[u], num[v]); else { DFS(v); low[u] = min(low[u], low[v]); } } if (num[u] == low[u]) { scc++; do { v = st[top--]; lab[v] = scc; was[v] = true; } while (v != u); } } int main() { scanf("%d %d\n", &n, &m); int i, u, v, source = 0, sink = 0, s, t; for(i=1; i<=m; i++) { scanf("%d %d\n", &u, &v); a[u].push_back(v); } for(i=1; i<=n; i++) if (num[i] == 0) DFS(i); for(u=1; u<=n; u++) for(i=0; i<a[u].size(); i++) { v = a[u][i]; if (lab[u] != lab[v]) { in[lab[v]]++; out[lab[u]]++; } } for(i=1; i<=scc; i++) { if (in[i] == 0) { source++; s = i; } if (out[i] == 0) { sink++; t = i; } } if (source != 1 || sink != 1) printf("NO"); else { printf("YES\n"); for(i=1; i<=n; i++) if (lab[i] == s) {s = i; break;} for(i=1; i<=n; i++) if (lab[i] == t) {t = i; break;} printf("%d %d", t, s); } return 0; }
Code mẫu của RR
const FINP=''; FOUT=''; var f1,f2:text; vao,ra:array [1..2000] of byte; n,m:longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i,x,y:longint; begin readln(f1,n,m); for i:=1 to m do begin readln(f1,x,y); vao[y]:=1; ra[x]:=1; end; end; procedure ans; var i,u,v,count:longint; begin count:=0; for i:=1 to n do begin if vao[i]=0 then begin u:=i; inc(count); end else if ra[i]=0 then begin v:=i; inc(count); end; if count=2 then break; end; writeln(f2,'YES'); write(f2,v,' ',u); end; begin openF; inp; ans; closeF; end.
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <ctime> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <iostream> #include <map> #include <set> #include <sstream> #include <stack> #include <queue> #include <vector> #include <utility> using namespace std; int num[2020],low[2020],lab[2020],pos[2020],cnt = 0,com = 0; int n,m,x[30010],y[30010]; stack<int> s; map< pair<int,int>,bool > mp; bool in[2020],ou[2020],used[2020]; vector<int> adj[2020]; void DFS(int u) { num[u] = low[u] = ++cnt; s.push(u); for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (!used[v]) continue; if (!num[v]) { DFS(v); low[u] = min(low[u],low[v]); } else low[u] = min(low[u],num[v]); } if (num[u] == low[u]) { com++; while (1) { lab[com] = s.top(); s.pop(); pos[lab[com]] = com; used[lab[com]] = false; if (lab[com] == u) break; } } } int main() { // freopen("nkonearc.in","r",stdin); // freopen("nkonearc.ou","w",stdout); scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d %d", &x[i], &y[i]); if (x[i] == y[i] || mp[make_pair(x[i],y[i])]) continue; mp[make_pair(x[i],y[i])] = true; adj[x[i]].push_back(y[i]); } memset(used,true,sizeof(used)); memset(in,true,sizeof(in)); memset(ou,true,sizeof(ou)); for (int i = 1; i <= n; i++) if (used[i]) DFS(i); for (int i = 0; i < m; i++) if (pos[x[i]] != pos[y[i]]) { ou[pos[x[i]]] = false; in[pos[y[i]]] = false; } int fin = 1,fou = 1; for (int i = 1; i <= com; i++) { if (in[i]) fin = lab[i]; if (ou[i]) fou = lab[i]; } printf("YES\n"); printf("%d %d\n", fou, fin); }
Code mẫu của skyvn97
#include<cstdio> #include<stack> #include<vector> #define MAX 200200 #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1) #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1) #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) using namespace std; vector<int> g[MAX]; int n,m,cnt,nComp; int low[MAX],num[MAX],compID[MAX]; bool fre[MAX],isRoot[MAX],isLeaf[MAX]; stack<int> st; inline void minimize(int &x,const int &y) { if (x>y) x=y; } void loadgraph(void) { scanf("%d%d",&n,&m); REP(zz,m) { int u,v; scanf("%d%d",&u,&v); g[u].push_back(v); } FOR(i,1,n) fre[i]=true; } void visit(int u) { low[u]=num[u]=++cnt; st.push(u); FORE(it,g[u]) if (fre[*it]) { int v=*it; if (num[v]==0) { visit(v); minimize(low[u],low[v]); } else minimize(low[u],num[v]); } if (low[u]==num[u]) { nComp++; int v; do { v=st.top();st.pop(); fre[v]=false; compID[v]=nComp; } while (v!=u); } } void process(void) { FOR(i,1,n) if (num[i]==0) visit(i); FOR(i,1,nComp) isRoot[i]=isLeaf[i]=true; FOR(u,1,n) FORE(it,g[u]) { int v=*it; if (compID[u]!=compID[v]) isRoot[compID[v]]=isLeaf[compID[u]]=false; } FOR(i,1,nComp) if (isRoot[i]) FOR(j,1,nComp) if (isLeaf[j]) FOR(u,1,n) if (compID[u]==i) FOR(v,1,n) if (compID[v]==j) { printf("YES\n%d %d",v,u); return; } } int main(void) { loadgraph(); process(); return 0; }
Comments