Hướng dẫn giải của Truyền tin
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=800; var n,m,re,res,dem,last:longint; a:array[1..maxn,1..maxn] of longint; d,low,st,r,st1:array[1..maxn] of longint; free:array[1..maxn] of boolean; procedure rf; var i,j,x,y:longint; begin assign(input,fi); reset(input); readln(n,m); for i:=1 to m do begin readln(x,y); a[x,y]:=1; end; close(input); end; procedure push(i:longint); begin inc(last); st[last]:=i; end; function pop:longint; begin pop:=st[last]; dec(last); end; function min(t,u:longint):longint; begin if t<u then min:=t else min:=u; end; procedure visit(i:longint); var k,j,sl:longint; kt:boolean; begin inc(dem); d[i]:=dem; low[i]:=d[i]; push(i); for j:=1 to n do if free[j] and (a[i,j]=1) then if d[j]>0 then low[i]:=min(low[i],d[j]) else begin visit(j); low[i]:=min(low[i],low[j]); end; if d[i]=low[i] then begin inc(re); sl:=0; repeat j:=pop; inc(sl); st1[sl]:=j; free[j]:=false; r[j]:=re; until j=i; for j:=1 to n do if r[j]<>re then begin kt:=true; for k:=1 to sl do if a[j,st1[k]]=1 then begin kt:=false; break; end; if not kt then break; end; if kt then inc(res); end; end; procedure pr; var i:longint; begin last:=0; dem:=0; re:=0; fillchar(free,sizeof(free),true); for i:=1 to n do if d[i]=0 then visit(i); end; procedure wf; var i:longint; begin assign(output,fo); rewrite(output); writeln(res); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include<bits/stdc++.h> using namespace std; #define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i) const int N = 800, INF = 1e9; vector<int> g[N]; int degIn[N], iscc[N], nscc, n, m; int timed, low[N], d[N]; void enter() { cin >> n >> m; for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; g[u-1].push_back(v-1); } } stack<int> st; void dfs(int u) { st.push(u); d[u] = low[u] = timed++; TR(g[u], v) if(d[*v] == -1) dfs(*v), low[u] = min(low[u], low[*v]); else low[u] = min(low[u], d[*v]); if(low[u] == d[u]) { int v; do { v = st.top(); st.pop(); iscc[v] = nscc; } while(u != v); ++nscc; } d[u] = INF; } void buildSuperGraph() { for(int u = 0; u < n; ++u) TR(g[u], v) if(iscc[u] != iscc[*v]) ++degIn[iscc[*v]]; } int main() { ios::sync_with_stdio(false); enter(); fill(d, d+n, -1); for(int u = 0; u < n; ++u) if(d[u] == -1) dfs(u); buildSuperGraph(); cout << count(degIn, degIn+nscc, 0) << '\n'; return 0; }
Code mẫu của ladpro98
program messageVOJ; uses math; const maxn=888; maxm=sqr(maxn); oo=123456789; fi=''; type e=record v,link:longint; end; var adj,assc,rassc:array[1..maxm] of e; head,hssc,rhssc,num,low,stack,ssc,topo:array[1..maxn] of longint; avail:array[1..maxn] of boolean; n,m,count,ls,cs,dssc,drssc,i,res:longint; procedure input; var inp:text; i,x,y:longint; begin assign(inp,fi); reset(inp); readln(inp,n,m); for i:=1 to m do begin readln(inp,x,y); adj[i].v:=y; adj[i].link:=head[x]; head[x]:=i; end; close(inp); end; procedure TarjanDfs(u:longint); var i:longint; v:e; begin inc(count);num[u]:=count;low[u]:=oo; inc(ls);stack[ls]:=u; i:=head[u]; while i<>0 do begin v:=adj[i]; if avail[v.v] then begin if num[v.v]>0 then low[u]:=min(low[u],num[v.v]) else begin TarjanDfs(v.v); low[u]:=min(low[u],low[v.v]); end; end; i:=v.link; end; if low[u]>=num[u] then begin inc(cs); repeat i:=stack[ls];dec(ls); ssc[i]:=cs; avail[i]:=false; until i=u; end; end; procedure makeGssc; var i,j:longint; begin for i:=1 to n do begin j:=head[i]; while j<>0 do begin if ssc[adj[j].v]<>ssc[i] then begin inc(dssc); assc[dssc].v:=ssc[adj[j].v]; assc[dssc].link:=hssc[ssc[i]]; hssc[ssc[i]]:=dssc; inc(drssc); rassc[drssc].v:=ssc[i]; rassc[drssc].link:=rhssc[ssc[adj[j].v]]; rhssc[ssc[adj[j].v]]:=drssc; end; j:=adj[j].link; end; end; end; procedure topoDfs(v:longint); var i:longint; begin avail[v]:=false; i:=rhssc[v]; while i<>0 do begin if avail[rassc[i].v] then topoDfs(rassc[i].v); i:=rassc[i].link; end; inc(count); topo[count]:=v; end; procedure dfs(u:longint); var i:longint; begin avail[u]:=false; i:=hssc[u]; while i>0 do begin if avail[assc[i].v] then dfs(assc[i].v); i:=assc[i].link; end; end; begin input; for i:=1 to n do avail[i]:=true; for i:=1 to n do if avail[i] then TarjanDfs(i); makeGssc; for i:=1 to cs do avail[i]:=true; count:=0; for i:=1 to cs do if avail[i] then topoDfs(i); for i:=1 to cs do avail[i]:=true; for i:=1 to count do if avail[topo[i]] then begin inc(res); dfs(topo[i]); end; write(res); end.
Code mẫu của RR
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <cstring> #include <cstdlib> #include <cmath> #include <string> #include <memory.h> #include <sstream> #include <complex> #include <iomanip> #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 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 FOREACH(it,c) for (__typeof((c).begin()) it=(c).begin();it!=(c).end();it++) #define RESET(c,x) memset (c, x, sizeof (c)) #define sqr(x) ((x) * (x)) #define PB push_back #define MP make_pair #define F first #define S second #define ALL(c) (c).begin(), (c).end() #define SIZE(c) (c).size() #define DEBUG(x) { cerr << #x << " = " << x << endl; } #define PR(a,n) {cerr<<#a<<" = "; FOR(_,1,n) cerr << a[_] << ' '; cerr <<endl;} #define PR0(a,n) {cerr<<#a<<" = ";REP(_,n) cerr << a[_] << ' '; cerr << endl;} using namespace std; const double PI = 2.0 * acos (0.0); typedef long long LL; typedef pair <int, int> PII; template <class T> inline T MAX (T a, T b) { if (a > b) return a; return b; } template <class T> inline T MIN (T a, T b) { if (a < b) return a; return b; } // ptrrsn_1's template const int MAXV = 1011; int dfs_num[MAXV + 5], dfs_low[MAXV + 5], visited[MAXV + 5]; int dfsNumberCounter, numSCC; int V; vector <int> S; vector <int> G[MAXV + 5]; vector <int> ls[MAXV + 5]; int reg[MAXV + 5]; bool vao[MAXV + 5]; void tarjanSCC(int u) { dfs_low[u] = dfs_num[u] = dfsNumberCounter++; S.PB(u); visited[u] = 1; REP (j, SIZE(G[u])) { int v = G[u][j]; if (dfs_num[v] == -1) tarjanSCC(v); if (visited[v]) dfs_low[u] = min(dfs_low[u], dfs_low[v]); } if (dfs_low[u] == dfs_num[u]) { ++numSCC; while (1) { int v = S.back(); S.pop_back(); visited[v] = 0; ls[numSCC].PB(v); reg[v] = numSCC; if (u == v) break; } } } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif scanf("%d", &V); int m; scanf("%d", &m); while (m--) { int u, v; scanf("%d%d", &u, &v); --u; --v; G[u].PB(v); } RESET(dfs_num, -1); RESET(dfs_low, 0); RESET(visited, 0); dfsNumberCounter = numSCC = 0; REP (i, V) if (dfs_num[i] == -1) tarjanSCC(i); REP(u,V) REP(i,G[u].size()) { int v = G[u][i]; if (reg[u] != reg[v]) vao[reg[v]] = true; } int res = 0; FOR(i,1,numSCC) if (!vao[i]) ++res; printf("%d\n", res); return 0; }
Code mẫu của ll931110
{$MODE DELPHI} Program MESS; Const input = ''; output = ''; maxn = 800; Var a: array[1..maxn,1..maxn] of boolean; free: array[1..maxn] of boolean; list,num: array[1..maxn] of integer; n,m,count: integer; Procedure init; Var f: text; i,u,v: integer; Begin Assign(f, input); Reset(f); Readln(f, n, m); Fillchar(a, sizeof(a), false); For i:= 1 to m do Begin Readln(f, u, v); a[u,v]:= true; End; Close(f); End; Procedure visit(u: integer); Var v: integer; Begin free[u]:= false; For v:= 1 to n do if a[u,v] and free[v] then Begin free[v]:= false; visit(v); End; inc(count); list[u]:= count; End; Procedure solve; Var f: text; i,res: integer; Begin count:= 0; Fillchar(free, sizeof(free), true); For i:= 1 to n do if free[i] then visit(i); For i:= 1 to n do num[list[i]]:= i; res:= 0; Fillchar(free, sizeof(free), true); For i:= n downto 1 do if free[num[i]] then Begin inc(res); visit(num[i]); End; Assign(f, output); Rewrite(f); Writeln(f, res); Close(f); End; Begin init; solve; End.
Code mẫu của khuc_tuan
#include "iostream" using namespace std; int n,m; bool a[888][888]; bool mark[888], visited[888]; void dfs(int i){ visited[i]=true; for(int j=1;j<=n;++j) if(a[i][j] && !visited[j]){ dfs(j); } } int main() { int u,v,dem=0; scanf("%d%d",&n,&m); for(int i=0;i<m;++i){ scanf("%d%d",&u,&v); a[u][v]=true; } for(int i=1;i<=n;++i) if(!visited[i]){ mark[i]=true; dfs(i); } memset( visited, 0, sizeof(visited)); for(int i=n;i>=1;--i) if(mark[i] && !visited[i]){ ++dem; dfs(i); } cout << dem << endl; return 0; }
Bình luận