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.

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

Please read the guidelines before commenting.


There are no comments at the moment.