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

#include<iostream>
#include<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define maxm 22222
#define maxn 16016
using namespace std;

int n,m,b[maxm],c[maxm],a[maxm*2],p[maxn],d[maxn],sm,cnt,low[maxn],num[maxn];
int last,st[maxn],f[maxn],aa[maxm*2],pp[maxn],l[maxn],pl[maxn],rev[maxn],e[maxn];

void visit(int x)
{
    int i;
    num[x]=++cnt; low[x]=cnt; st[++last]=x;
    fr(i,p[x]+1,p[x+1])
      if (!d[a[i]])
      {
         if (num[a[i]]) low[x]=min(low[x],num[a[i]]);
         else 
         {
            visit(a[i]);
            low[x]=min(low[x],low[a[i]]);
         }
      }
    if (num[x]<=low[x])
    {
       sm++;
       do
       {
          i=st[last--]; d[i]=sm; 
       } while (i!=x);
    }
}

void go(int x)
{
    int i;
    fr(i,pp[x]+1,pp[x+1]) 
    {
       if (!e[aa[i]]) go(aa[i]);
       if (!f[aa[i]]) f[x]=0;
    }
    e[x]=1;
    if (f[x]<0) 
    {
       f[x]=1;
       fr(i,pl[x]+1,pl[x+1]) f[l[i]]=0;
    }
}

int main()
{
    int i,x,y;
    cin >> m >> n;
    fr(i,1,n*2)
      if (i<=n) rev[i]=i+n;
      else rev[i]=i-n;
    fr(i,1,m)
    {
       scanf("%d%d",&x,&y);
       if (x<0) x=n-x;
       if (y<0) y=n-y;
       b[i]=x; c[i]=y;
       p[rev[x]]++; p[rev[y]]++;
    }
    fr(i,2,n*2+1) p[i]+=p[i-1];
    fr(i,1,m)
    {
       a[p[rev[b[i]]]--]=c[i];
       a[p[rev[c[i]]]--]=b[i];
    }   
    //strongly-connected components
    fr(i,1,n*2)
      if (!d[i]) visit(i);
    //check condition + create opposite vertex
    fr(i,1,n)
      if (d[i]==d[i+n])
      {
         cout << "NO" << endl;
         return 0;
      }
      else
      {
         pl[d[i]]++; pl[d[i+n]]++;
      }
    fr(i,2,sm+1) pl[i]+=pl[i-1];
    fr(i,1,n)
    {
       l[pl[d[i]]--]=d[i+n];
       l[pl[d[i+n]]--]=d[i];
    }
    //union
    fr(i,1,m)
    {
       if (d[rev[b[i]]]!=d[c[i]]) pp[d[rev[b[i]]]]++;
       if (d[rev[c[i]]]!=d[b[i]]) pp[d[rev[c[i]]]]++;
    }
    fr(i,2,sm+1) pp[i]+=pp[i-1];
    fr(i,1,m)
    {
       if (d[rev[b[i]]]!=d[c[i]]) aa[pp[d[rev[b[i]]]]--]=d[c[i]];
       if (d[rev[c[i]]]!=d[b[i]]) aa[pp[d[rev[c[i]]]]--]=d[b[i]];
    }
    //topo + find result
    fr(i,1,sm) f[i]=-1;
    fr(i,1,sm)
       if (!e[i]) go(i);
    //output
    int sl=0;
    fr(i,1,n) sl+=f[d[i]];
    cout << "YES" << endl;
    cout << sl << endl;
    fr(i,1,n)
       if (f[d[i]]) cout << i << " ";
    cout << endl; 
    return 0;
}

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 M = 8000, INF = 1e9;
int n, m, d[2*M], low[2*M], iscc[2*M], nscc, timed;
vector<int> g[2*M], scc[2*M], sg[2*M];
bool choosescc[2*M];

int getVertice(int u) {
    return (abs(u)-1) << 1 | (u < 0 ? 1 : 0);
}

void enter() {
    cin >> n >> m;
    for(int i = 0; i < n; ++i) {
        int u, v; cin >> u >> v;
        u = getVertice(u); v = getVertice(v);
        g[u ^ 1].push_back(v);
        g[v ^ 1].push_back(u);
    }
}

stack<int> st;
void dfs(int u) {
    st.push(u);
    low[u] = d[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;
            scc[nscc].push_back(v);
        } while (v != u);
        ++nscc;
    }
    d[u] = INF;
}

void makeSuperGraph() {
    for(int u = 0; u < 2*m; ++u)
        TR(g[u], v)
            sg[iscc[u]].push_back(iscc[*v]);
}

bool mayHasSolution() {
    for(int u = 0; u < m; ++u)
        if(iscc[u << 1] == iscc[u << 1 | 1])
            return false;
    return true;
}

void StrongConnectedComponent() {
    fill(d, d+2*m, -1);
    for(int u = 0; u < 2*m; ++u)
        if(d[u] == -1) dfs(u);
}

void trace() {
    fill(choosescc, choosescc + nscc, true);
    for(int i = 0; i < nscc; ++i) if(choosescc[i])
        TR(scc[i], u) choosescc[iscc[*u ^ 1]] = false;
    int res = 0;
    for(int u = 0; u < m; ++u) if(choosescc[iscc[u << 1]])
        ++res;
    cout << "YES\n" << res << '\n';
    for(int u = 0; u < m; ++u) if(choosescc[iscc[u << 1]])
        cout << u+1 << ' ';
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    StrongConnectedComponent();
    if(mayHasSolution()) {
        makeSuperGraph();
        trace();
    } else cout << "NO\n";
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 50000;

using namespace std;
int lab[N], st[N], low[N], num[N], res[N];
vector<int> a[N], com[N];
bool was[N], val[N];
int n, m, gap, nn, cnt, top, scc, k;

void Enter() {
    scanf("%d %d\n", &m, &n);
    gap = n + 1; nn = n + gap;
    int i, v, u;
    for(i=1; i<=m; i++) {
        scanf("%d %d\n", &u, &v);
        a[-u + gap].push_back(v + gap);
        a[-v + gap].push_back(u + gap);
    }

}

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--];
            was[v] = true;
            lab[v] = scc;
            com[scc].push_back(v);
        } while (v != u);
    }
}

int main()
{
    Enter();
    int i, j, v; bool mustTrue;
    for(i=1; i<=nn; i++)
    if (num[i] == 0) DFS(i);
    for(i=1; i<=n; i++)
    if (lab[i + gap] == lab[-i + gap]) {
        printf("NO"); return 0;
    }
    for(i=scc; i; i--) {
        mustTrue = false;
        for(j=0; j<com[i].size(); j++)
        if (val[com[i][j]]) {mustTrue = true; break;}
        if (!mustTrue) {
            for(j=0; j<com[i].size(); j++) {
                v = com[i][j];
                v = -(v - gap) + gap;
                val[v] = true;
            }
        }
        else {
            for(j=0; j<com[i].size(); j++) {
                v = com[i][j];
                val[v] = true;
            }
        }
    }
    printf("YES\n");
    for(i=1; i<=n; i++)
    if (val[i + gap]) res[++k] = i;
    printf("%d\n", k);
    for(i=1; i<=k; i++) printf("%d ", res[i]);
    return 0;
}

Code mẫu của RR

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=20000;
  MAXM=16000;
type
  list=^node;
  node=record u:longint; next:list; end;
var
  hsize,sl,top,count,m,n:longint;
  free,tp,low,num:array[-MAXN..MAXN] of longint;
  choose,dd,stack,deg,h,hpos:array[1..MAXN*2] of longint;
  ke:array[-MAXN..MAXN] of list;
  ds,ke2:array[1..MAXN] of list;
procedure add(u:longint;var a:list); inline;
var
  p:list;
begin
  new(p); p^.u:=u;
  p^.next:=a; a:=p;
end;
procedure inp;
var
  f:text;
  i,u,v:longint;
  procedure finish; inline;
  begin
    close(f);
    assign(f,FOUT); rewrite(f);
    writeln(f,'NO');
    close(f);
    halt;
  end;
begin
  assign(f,FINP); reset(f);
  read(f,m,n);
  for i:=-n to n do ke[i]:=nil;
  for i:=1 to m do
    begin
      read(f,u,v);
      if u=-v then continue;
      if u=v then
        begin
          if u<0 then begin if choose[-u]=1 then finish; choose[-u]:=-1; end
          else begin if choose[u]=-1 then finish; choose[u]:=1; end;
          continue;
        end;
      add(v,ke[-u]);
      add(u,ke[-v]);
    end;
  close(f);
end;
procedure dfs1(u:longint); inline;
var
  v:longint;
  p:list;
begin
  inc(top); stack[top]:=u;
  inc(count); num[u]:=count; low[u]:=count;
  p:=ke[u];
  while p<>nil do
    begin
      v:=p^.u; p:=p^.next;
      if free[v]=1 then continue;
      if num[v]=0 then
        begin
          dfs1(v);
          low[u]:=min(low[u],low[v]);
        end
      else low[u]:=min(low[u],num[v]);
    end;
  if num[u]=low[u] then
    begin
      inc(sl);
      ds[sl]:=nil;
      repeat
        v:=stack[top]; dec(top);
        tp[v]:=sl;
        free[v]:=1;
        add(v,ds[sl]);
      until v=u;
    end;
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i shl 1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (deg[h[j+1]]<deg[h[j]]) then inc(j);
      if (deg[h[j]]<deg[h[i]]) then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i shl 1;
    end;
end;
procedure upHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i shr 1;
  while (i>1) and (deg[h[i]]<deg[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push(u:longint); inline;
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u:longint); inline;
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]);
  hpos[h[1]]:=0;
  dec(hsize); downHeap(1);
end;
procedure dfs2(u:longint); inline;
var
  p:list;
  v:longint;
begin
  if dd[u]=1 then exit;
  p:=ke2[u]; dd[u]:=1;
  while p<>nil do
    begin
      v:=p^.u; p:=p^.next;
      if dd[v]=1 then continue;
      dfs2(v);
    end;
end;
procedure finish; inline;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,'NO');
  close(f);
  halt;
end;
procedure solve;
var
  i,u,v:longint;
  p,pp:list;
  f:text;
begin
  count:=0;
  {Xay dung cac thanh phan lien thong manh}
  for i:=-n to n do
  if i<>0 then
    if num[i]=0 then dfs1(i);
  {Neu co thanh phan lien thong chua ca dinh u va -u thi dung lai}
  for i:=1 to n do
    if tp[i]=tp[-i] then finish;
  {Tao do thi voi cac dinh la cac thanh phan lien thong manh}
  fillchar(dd,sizeof(dd),0);
  for i:=1 to sl do
    begin
      p:=ds[i];
      while p<>nil do
        begin
          u:=p^.u; p:=p^.next;
          pp:=ke[u];
          while pp<>nil do
            begin
              v:=pp^.u; pp:=pp^.next;
              if tp[v]=i then continue;
              add(i,ke2[tp[v]]);
              inc(deg[i]);
            end;
        end;
    end;
  {sort topo}
  hsize:=0;
  for i:=1 to sl do
    if dd[i]=0 then push(i);
  top:=0;
  while hsize>0 do
    begin
      pop(u);
      inc(top); stack[top]:=u;
      p:=ke2[u];
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          if dd[v]=1 then continue;
          dec(deg[v]);
          upHeap(hpos[v]);
        end;
    end;
  {Xu ly}
  for i:=1 to n do
    if choose[i]=1 then
      begin
        tp[i]:=1;
        for u:=-n to n do
        if tp[u]=tp[i] then
          begin
            if u<0 then choose[-u]:=-1
            else choose[u]:=1;
            dfs2(tp[-u]);
          end;
      end;
  for i:=1 to sl do
    begin
      u:=stack[i];
      if dd[u]=1 then continue;
      dd[u]:=1;
      p:=ds[u];
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          if v<0 then begin if choose[-v]=1 then finish; choose[-v]:=-1; end
          else begin if choose[v]=-1 then finish; choose[v]:=1; end;
          dfs2(tp[-v]);
        end;
    end;
  assign(f,FOUT); rewrite(f);
  for i:=1 to n do
    if choose[i]=0 then
      begin
        writeln(f,'NO');
        close(f);
        halt;
      end;
  sl:=0;
  for i:=1 to n do if choose[i]=1 then inc(sl);
  writeln(f,'YES');
  writeln(f,sl);
  for i:=1 to n do if choose[i]=1 then write(f,i,' ');
  close(f);
end;
begin
  inp;
  solve;
end.

Code mẫu của ll931110

//#pragma comment(linker, "/STACK:16777216")
#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[20010],low[20010],mark[20010],pos[20010],ou[20010],lab[20010];
bool exist[20010];
int m,n;
int cnt,com = 0;
bool choose[20010];
vector< pair<int,int> > edge;
vector<int> adj[20010],rev[20010],element[20010];
stack<int> s;
map< pair<int,int>,bool > mp;

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 (!exist[v]) continue;
        if (num[v] < 0)
        {
            DFS(v);  low[u] = min(low[u],low[v]);
        }
        else low[u] = min(low[u],num[v]);
    }
    if (low[u] == num[u])
    {
        while (1)
        {
            int x = s.top();  s.pop();  
            pos[x] = com;  element[com].push_back(x);  exist[x] = false;  if (x == u) break;
        }
        com++;
    }
}

void toposort()
{
    cnt = -1;
    queue<int> q;
    for (int i = 0; i < com; i++) if (!ou[i]) q.push(i);
    while (!q.empty())
    {
        int u = q.front();  q.pop();  lab[++cnt] = u;
        for (int i = 0; i < rev[u].size(); i++)
        {
            int v = rev[u][i];  ou[v]--;  if (!ou[v]) q.push(v);
        }
    }
}

void mark_false(int u)
{
    for (int i = 0; i < rev[u].size(); i++)
    {
        int v = rev[u][i];
        if (mark[v] < 0)
        {
            mark[v] = 0;  mark_false(v);
        }
    }
}

int main()
{
//    freopen("twosat.in","r",stdin);
//    freopen("twosat.ou","w",stdout);
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        int u,v;  scanf("%d %d", &u, &v);
        if (u > 0) u = 2 * (u - 1); else u = 2 * (-u - 1) + 1;
        if (v > 0) v = 2 * (v - 1); else v = 2 * (-v - 1) + 1;
        if ( (u ^ v) == 1) continue;
        edge.push_back(make_pair(u ^ 1,v));
        adj[u ^ 1].push_back(v);        
        edge.push_back(make_pair(v ^ 1,u));
        adj[v ^ 1].push_back(u);
    }    

    memset(num,-1,sizeof(num));
    cnt = -1;
    memset(exist,true,sizeof(exist));
    for (int i = 0; i < 2 * n; i++) if (num[i] < 0) DFS(i);

    for (int i = 0; i < n; i++) if (pos[2 * i] == pos[2 * i + 1])
    {
        printf("NO\n");  return 0;
    }

    for (int i = 0; i < com; i++) adj[i].clear();
    memset(ou,0,sizeof(ou));
    for (vector< pair<int,int> >::iterator it = edge.begin(); it != edge.end(); it++)
    {
        int u = pos[it->first],v = pos[it->second];
        if (u == v || mp[make_pair(u,v)]) continue;
        mp[make_pair(u,v)] = true;  
        ou[u]++;  adj[u].push_back(v);  rev[v].push_back(u);
    }
    toposort();

    memset(mark,-1,sizeof(mark));
    for (int i = 0; i < com; i++) if (mark[lab[i]] < 0)
    {
        mark[lab[i]] = 1;
        int first_element = element[lab[i]][0];
        int alter = pos[first_element ^ 1];
        mark[alter] = 0;  mark_false(alter);
    }

    memset(choose,false,sizeof(choose));
    for (int i = 0; i < com; i++) if (mark[i] > 0)
      for (int j = 0; j < element[i].size(); j++) if (element[i][j] % 2 == 0) choose[element[i][j]/2] = true;

    vector<int> ret;
    for (int i = 0; i < n; i++) if (choose[i]) ret.push_back(i + 1);
    printf("YES\n");
    printf("%d\n", ret.size());
    for (int i = 0; i < ret.size(); i++) printf("%d ", ret[i]);
}

Code mẫu của skyvn97

#include<cstdio>
#include<stack>
#include<vector>
#include<cstring>
#include<algorithm>
#define MAXN   8000
#define x   first
#define y   second
using namespace std;
typedef pair<int,int> ii;
stack<int> st;
//for the first graph
int m,n;
vector<int> g[2*MAXN+7];
int low[2*MAXN+7];
int num[2*MAXN+7];
int ncp[2*MAXN+7];
bool fre[2*MAXN+7];
int res[2*MAXN+7];
int time;
//for the second graph
int nc;
vector<int> h[2*MAXN+7];
vector<int> comp[2*MAXN+7];
int cnt;
int topo[2*MAXN+7];
bool vst[2*MAXN+7];
int mark[2*MAXN+7];
ii lst[2*MAXN+7];
void loadgraph_1st(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    int i,u,v;
    for (i=1;i<=n;i=i+1) {
        g[i].clear();
        g[i+n].clear();
    }
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        if (u>0 && v>0) {
            g[u+n].push_back(v);
            g[v+n].push_back(u);
        }
        if (u>0 && v<0) {
            v=-v;
            g[u+n].push_back(v+n);
            g[v].push_back(u);
        }
        if (u<0 && v>0) {
            u=-u;
            g[u].push_back(v);
            g[v+n].push_back(u+n);
        }
        if (u<0 && v<0) {
            u=-u;v=-v;
            g[u].push_back(v+n);
            g[v].push_back(u+n);
        }
    }
    memset(fre,true,sizeof fre);
    memset(low,0,sizeof low);
    memset(num,0,sizeof num);
    time=0;
    nc=0;
    while (!st.empty()) st.pop();
}
int min(const int &x,const int &y) {
    if (x<y) return (x); else return (y);
}
void visit_1st(const int &u) {
    int i,v;
    time++;
    num[u]=time;
    low[u]=num[u];
    st.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_1st(v);
                low[u]=min(low[u],low[v]);
            }
        }
    }
    if (low[u]==num[u]) {
        nc++;
        comp[nc].clear();
        do {
            v=st.top();st.pop();
            fre[v]=false;
            ncp[v]=nc;
            comp[nc].push_back(v);
        }
        while (v!=u);
    }
}
void tarjan(void) {
    int i;
    for (i=1;i<=2*n;i=i+1)
        if (num[i]==0) visit_1st(i);
    for (i=1;i<=n;i=i+1)
        if (ncp[i]==ncp[i+n]) {
            printf("NO");
            exit(0);
        }
}
void loadgraph_2nd(void) {
    int i,j;
    for (i=1;i<=nc;i=i+1) h[i].clear();
    for (i=1;i<=2*n;i=i+1)
        for (j=0;j<g[i].size();j=j+1)
            h[ncp[i]].push_back(ncp[g[i][j]]);
    cnt=nc;
    memset(vst,true,sizeof vst);
}
void visit_2nd(const int &u) {
    int i,v;
    for (i=0;i<h[u].size();i=i+1) {
        v=h[u][i];
        if (vst[v]) {
            vst[v]=false;
            visit_2nd(v);
        }
    }
    cnt--;
    topo[u]=cnt;
    lst[u]=ii(-topo[u],u);
}
void sort_topo(void) {
    int i,j,u,v;
    for (i=1;i<=nc;i=i+1)
        if (vst[i]) {
            vst[i]=false;
            visit_2nd(i);
        }
    memset(mark,-1,sizeof mark);
    sort(&lst[1],&lst[nc+1]);
    for (i=1;i<=nc;i=i+1) {
        u=lst[i].y;
        if (mark[u]>=0) continue;
        mark[u]=1;
        for (j=0;j<comp[u].size();j=j+1) {
            v=comp[u][j];
            if (v>n) mark[ncp[v-n]]=0;
            else mark[ncp[v+n]]=0;
        }
    }
}
void print(void) {
    int i,j;
    int nk=0;
    for (i=1;i<=2*n;i=i+1) res[i]=mark[ncp[i]];
    for (i=1;i<=n;i=i+1) nk+=res[i];
    printf("YES\n%d\n",nk);
    j=0;
    for (i=1;i<=n;i=i+1)
        if (res[i]==1) {
            printf("%d",i);
            j++;
            if (j<nk) printf(" ");
        }
    printf("\nSang thuc giac thay sao dep hon hom qua :D");
}
int main(void) {
    loadgraph_1st();
    tarjan();
    loadgraph_2nd();
    sort_topo();
    print();
    return 0;
}