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.

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

Please read the guidelines before commenting.


There are no comments at the moment.