Editorial for Tìm TPLT mạ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
uses math; var n,m,i,j,sm,cnt,last:longint; p,st,low,num:array[1..10010] of longint; a,b,c:array[1..100010] of longint; d:array[1..10010] of boolean; procedure visit(x:longint); var i:longint; begin inc(cnt); num[x]:=cnt; low[x]:=cnt; inc(last); st[last]:=x; for i:=p[x]+1 to p[x+1] do if not d[a[i]] then begin if num[a[i]]>0 then low[x]:=min(low[x],num[a[i]]) else begin visit(a[i]); low[x]:=min(low[x],low[a[i]]); end; end; if low[x]=num[x] then begin inc(sm); repeat i:=st[last]; dec(last); d[i]:=true; until i=x; end; end; begin read(n,m); for i:=1 to m do begin read(b[i],c[i]); inc(p[b[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]]); end; for i:=1 to n do if not d[i] then visit(i); writeln(sm); end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #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 fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N vvi g; //graph vii e; //edge e[i].first = e[i].lowlink, e[i].second = e[i].index int n, m, idx, res; bool inS[10005]; stack<int> s; void dfs(int u) { e[u].fi = e[u].se = idx++; inS[u] = 1; s.push(u); tr(g[u],it) if( e[*it].se == -1 ) { dfs(*it); e[u].fi = min( e[u].fi, e[*it].fi ); } else if( inS[*it] ) e[u].fi = min( e[u].fi, e[*it].se ); if( e[u].fi == e[u].se ) { ++res; int v; do { v = s.top(); s.pop(); inS[v] = 0; } while( u != v ); } } int main() { scanf( "%d%d", &n, &m ); g = vvi(n, vi()); e = vii(n, ii(-1,-1)); rep(i,m) { int u, v; scanf( "%d%d", &u, &v ); g[--u].push_back(--v); } rep(i,n) if(e[i].se == -1) dfs(i); printf( "%d\n", res ); return 0; }
Code mẫu của ladpro98
#include <iostream> #include <cstdio> #include <algorithm> #include <stdio.h> #include <stack> #define maxn 10004 #define maxm 100005 #define oo 123456789; using namespace std; int adj[maxm]; int head[maxn]; int linker[maxm]; int d[maxn]; int low[maxn]; bool avail[maxn]; stack<int> s; int n, m, ssc, timer; void init() { int x,y; //freopen("tjalg.in","r",stdin); scanf("%d %d", &n, &m); for(int i=1; i<=m; i++) { scanf("%d %d", &x, &y); adj[i] = y; linker[i] = head[x]; head[x] = i; } for(int i=1; i<=n; i++) avail[i] = true; timer = 0; ssc = 0; } void dfs(int u) { timer++; d[u] = timer; low[u] = oo; s.push(u); int i = head[u]; int v; while (i!=0) { v = adj[i]; if (avail[v]) { if (d[v]>0) low[u] = min(low[u], d[v]); else { dfs(v); low[u] = min(low[u], low[v]); } } i = linker[i]; } if (low[u]>=d[u]) { ssc++; do{ v = s.top(); avail[v] = false; s.pop(); } while (v!=u); } } int main() { init(); for(int i=1; i<=n; i++) if (avail[i]) dfs(i); printf("%d",ssc); return 0; }
Code mẫu của RR
uses math; type list=^node; node=record u:longint; next:list; end; procedure add(u:longint; var a:list); var p:list; begin new(p); p^.u:=u; p^.next:=a; a:=p; end; var n,m,i,u,v,top:longint; low,num,stack,father:array[1..10111] of longint; ke:array[1..10111] of list; erased:array[1..10111] of boolean; cnt,res:longint; procedure dfs(u:longint); var v:longint; p:list; begin inc(cnt); low[u]:=cnt; num[u]:=cnt; inc(top); stack[top]:=u; p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if erased[v] then continue; if v=father[u] then continue; if num[v]=0 then begin father[v]:=u; dfs(v); low[u]:=min(low[u],low[v]); end else low[u]:=min(low[u],num[v]); end; if low[u]=num[u] then begin inc(res); repeat v:=stack[top]; dec(top); erased[v]:=true; until u=v; end; end; begin read(n,m); for i:=1 to m do begin read(u,v); add(v,ke[u]); end; fillchar(erased,sizeof(erased),false); for i:=1 to n do if num[i]=0 then begin cnt:=0; dfs(i); end; writeln(res); end.
Code mẫu của skyvn97
#include<cstdio> #include<vector> #define MAX 10101 using namespace std; int n,m,cnt,r; vector<int> g[MAX]; int num[MAX]; int low[MAX]; bool fre[MAX]; struct stack { int st[MAX]; int size; stack(){ size=0; } bool empty(void) { return (size==0); } void push(int x) { size++; st[size]=x; } int pop(void) { size--; return (st[size+1]); } }; int min(int x,int y) { if (x<y) return x; else return y; } stack s; void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); int i,u,v; for (i=1;i<=m;i=i+1) { scanf("%d",&u); scanf("%d",&v); g[u].push_back(v); } for (i=1;i<=n;i=i+1) { fre[i]=true; num[i]=0; } cnt=0; s=stack(); } void visit(int u) { int i,v; cnt++; num[u]=cnt; low[u]=cnt; s.push(u); for (i=0;i<g[u].size();i=i+1) { v=g[u][i]; if (fre[v]) { if (num[v]>0) low[u]=min(low[u],num[v]); else { visit(v); low[u]=min(low[u],low[v]); } } } if (low[u]==num[u]) { r=r+1; while (!s.empty()) { v=s.pop(); fre[v]=false; if (v==u) break; } } } void process(void) { int i; r=0; for (i=1;i<=n;i=i+1) if (num[i]==0) visit(i); printf("%d",r); //exit(0); } int main(void) { loadgraph(); process(); return 0; }
Comments