Hướng dẫn giải của VOI 06 Bài 5 - Mạng máy tính
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận