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 maxn 32032
#define maxm 72072
using namespace std;
int n,m,sm,cnt,rev[maxn],b[maxm],c[maxm],a[maxm*2],p[maxn],d[maxn],low[maxn],num[maxn];
int st[maxn],last,pl[maxn],l[maxn],pp[maxn],aa[maxm*2],f[maxn],e[maxn];

void visit(int x)
{
    int i; 
    st[++last]=x; low[x]=++cnt; num[x]=low[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;
    e[x]=1;
    fr(i,pp[x]+1,pp[x+1])
    {
       if (!e[aa[i]]) go(aa[i]);
       if (!f[aa[i]]) f[x]=0;
    }
    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 >> n >> m;
    n*=2;
    fr(i,1,n) 
    {
       rev[i]=i+n; rev[i+n]=i;
    }
    fr(i,1,m)
    {
       scanf("%d%d",&b[i],&c[i]);
       p[b[i]]++; p[c[i]]++;
    }    
    fr(i,1,n/2)
    {
       x=i*2-1; y=x+1;
       p[x]++; p[y]++; p[rev[x]]++; p[rev[y]]++;
       b[++m]=x; c[m]=y;
       b[++m]=rev[x]; c[m]=rev[y];
    }
    fr(i,2,n*2+1) p[i]+=p[i-1];
    fr(i,1,m)
    {
       a[p[b[i]]--]=rev[c[i]]; 
       a[p[c[i]]--]=rev[b[i]];
    }
    //strongly-connected components
    fr(i,1,n*2)
      if (!d[i]) visit(i);
    //check + create opposite vertex
    fr(i,1,n)
      if (d[i]==d[i+n])
      {
         cout << 0 << 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[b[i]]!=d[rev[c[i]]]) pp[d[b[i]]]++;
       if (d[c[i]]!=d[rev[b[i]]]) pp[d[c[i]]]++;
    }
    fr(i,2,sm+1) pp[i]+=pp[i-1];
    fr(i,1,m)
    {
       if (d[b[i]]!=d[rev[c[i]]]) aa[pp[d[b[i]]]--]=d[rev[c[i]]];
       if (d[c[i]]!=d[rev[b[i]]]) aa[pp[d[c[i]]]--]=d[rev[b[i]]];
    }
    //find result
    fr(i,1,sm) f[i]=-1;
    fr(i,1,sm)
      if (!e[i]) go(i);
    //out
    x=0;
    fr(i,1,n) x+=f[d[i]];
    if (x==n/2)
    {
       cout << 1 << endl;
       fr(i,1,n) 
         if (f[d[i]]) cout << i << " ";
         cout << endl;
    }
    else cout << 0 << 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 N = 8000, INF = 1e9;
int d[4*N], low[4*N], timed, n, m, iscc[4*N], nscc;
vector<int> g[4*N], scc[4*N];
bool choose[4*N];

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

stack<int> st;
void tarjan(int u) {
    d[u] = low[u] = timed++;
    st.push(u);
    TR(g[u], v) if(d[*v] == -1)
        tarjan(*v), low[u] = min(low[u], low[*v]);
    else
        low[u] = min(low[u], d[*v]);
    if(d[u] == low[u]) {
        int v;
        do {
            v = st.top(); st.pop();
            iscc[v] = nscc;
            scc[nscc].push_back(v);
        } while(u != v);
        ++nscc;
    }
    d[u] = INF;
}

bool hasSolution() {
    for(int i = 0; i < 2*n; ++i)
        if(iscc[i << 1] == iscc[i << 1 | 1])
            return false;
    return true;
}

void trace() {
    fill(choose, choose + nscc, true);
    for(int i = 0; i < nscc; ++i) if(choose[i])
        TR(scc[i], j) choose[iscc[*j ^ 1]] = false;
    cout << 1 << '\n';
    for(int i = 0; i < 2*n; ++i)
        if(choose[iscc[i << 1]])
            cout << i+1 << ' ';
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    fill(d, d+4*n, -1);
    for(int u = 0; u < 4*n; ++u) if(d[u] == -1) tarjan(u);
    if(hasSolution()) trace();
    else cout << 0 << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#define neg(a) ((a) ^ 1)
const int N = 50000;
const int oo = 2000000000;
using namespace std;
vector<int> a[N], scc[N];
int low[N], d[N], lab[N];
bool was[N], pick[N];
int n, m, timer, nscc;

void addEdge(int u, int v) {
    a[u].push_back(neg(v));
    a[neg(v)].push_back(u);
}

stack<int> S;
void DFS(int u) {
    d[u] = ++timer;
    low[u] = oo;
    S.push(u);
    for(int i = 0; i < a[u].size(); i++) {
        int v = a[u][i];
        if (was[v]) continue;
        if (d[v]) low[u] = min(low[u], d[v]);
        else {
            DFS(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] >= d[u]) {
        int v;
        do {
            v = S.top();
            scc[nscc].push_back(v);
            lab[v] = nscc;
            was[v] = true;
            S.pop();
        } while (v != u);
        nscc++; 
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int u, v;
    for(int i = 0; i < n; i++) {
        addEdge(i << 2, (i << 2) + 2);
        addEdge((i << 2) + 2, i << 2);
    }
    for(int i = 1; i <= m; i++) {
        cin >> u >> v; u--; v--; 
        a[u << 1].push_back(neg(v << 1));
        a[v << 1].push_back(neg(u << 1));
    }
    for(int i = 0; i < (n << 2); i++)
        if (!was[i]) DFS(i);
    for(int i = 0; i < (n << 2); i += 2)
        if (lab[i] == lab[neg(i)]) {cout << 0; return 0;}
    for(int i = nscc - 1; i >= 0; i--) {
        bool mustTrue = false;
        for(int j = 0; j < scc[i].size(); j++)
            if (pick[scc[i][j]]) {mustTrue = true; break;}
        if (mustTrue) 
            for(int j = 0; j < scc[i].size(); j++)
                pick[scc[i][j]] = true;
        else 
            for(int j = 0; j < scc[i].size(); j++)
                pick[neg(scc[i][j])] = true;
    }
    cout << 1 << endl;
    for(int i = 0; i < (n << 2); i += 2)
        if (pick[i]) cout << (i >> 1) + 1 << ' ';
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=8001;
type
  list=^node;
  node=record
         u:longint;
         next:list;
       end;
var
  free,num,low,tp:array[-MAXN..MAXN] of longint;
  dd,choose,deg,h,hpos,stack:array[1..MAXN*2] of longint;
  ke:array[-MAXN..MAXN] of list;
  ke2,ds:array[1..MAXN*2] of list;
  sl,hsize,m,n,count,top:longint;
procedure finish; inline;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,'0');
  close(f);
  halt;
end;
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;
begin
  assign(f,FINP); reset(f);
  read(f,n,m);
  for i:=-n to n do ke[i]:=nil;
  for i:=1 to m do
    begin
      read(f,u,v);
      if u and 1=1 then u:=-((u+1) shr 1) else u:=(u+1) shr 1;
      if v and 1=1 then v:=-((v+1) shr 1) else v:=(v+1) shr 1;
      if u=-v then continue;
      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]]:=1;
  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 solve;
var
  i,u,v:longint;
  p,pp:list;
  f:text;
begin
  count:=0; top:=0;
  for i:=-n to n do
  if i<>0 then
    if num[i]=0 then dfs1(i);
  for i:=1 to n do
    if tp[i]=tp[-i] then finish;
  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;
  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;
  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;
  for i:=1 to n do
    if choose[i]=0 then finish;
  assign(f,FOUT); rewrite(f);
  writeln(f,1);
  for i:=1 to n do
    if choose[i]=1 then write(f,i shl 1,' ')
    else write(f,i shl 1-1,' ');
  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("elect.in","r",stdin);
//    freopen("elect.ou","w",stdout);
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int u,v;  scanf("%d %d", &u, &v); u--;  v--;
        if ( (u ^ v) == 1) continue;
        edge.push_back(make_pair(u,v ^ 1));
        adj[u ^ 1].push_back(v);        
        edge.push_back(make_pair(v,u ^ 1));
        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("0\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;

    printf("1\n");
    for (int i = 0; i < n; i++) if (choose[i]) printf("%d ", 2 * i + 1); else printf("%d ", 2 * i + 2);
}

Code mẫu của skyvn97

#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define MAX   16161
#define f   first
#define s   second   
using namespace std;
typedef pair<int,int> ii;
stack<int> st;
//for the first graph
int m,n;
vector<int> g[MAX];
int low[MAX];
int num[MAX];
bool fre[MAX];
int ncp[MAX];
int res[MAX];
int time;
//for the second graph
int nc;
vector<int> comp[MAX];
vector<int> h[MAX];
int cnt;
bool vst[MAX];
int topo[MAX];
int mark[MAX];
ii lst[MAX];
void loadgraph_1st(void) {
    int i,j,u,v;
    scanf("%d",&n);
    scanf("%d",&m);
    for (i=1;i<=2*n;i=i+1) g[i].clear();
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        g[u/2+(n+1)*(u%2)].push_back(v/2+v%2+(1-v%2)*n);
        g[v/2+(n+1)*(v%2)].push_back(u/2+u%2+(1-u%2)*n);
    }
    memset(low,0,sizeof low);
    memset(num,0,sizeof num);
    memset(fre,1,sizeof fre);   
    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) {
    time++;
    num[u]=time;
    low[u]=num[u];
    st.push(u);
    int i,v;
    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("0");
            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]]);
    memset(vst,true,sizeof vst);
    memset(mark,-1,sizeof mark);
    cnt=nc;
}
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 findres(void) {
    int i,j,u,v;
    for (i=1;i<=nc;i=i+1)
        if (vst[i]) {
            vst[i]=false;
            visit_2nd(i);
        }
    sort(&lst[1],&lst[nc+1]);
    for (i=1;i<=nc;i=i+1) {
        u=lst[i].s;
        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;
    printf("1\n");
    for (i=1;i<=n;i=i+1) res[i]=mark[ncp[i]];
    for (i=1;i<=n;i=i+1) {
        if (res[i]==1) printf("%d",2*i);
        else printf("%d",2*i-1);
        if (i<n) printf(" ");
    }
    printf("\n");
    printf("Em co biet khong he ve phuong hong dep lam\n");
    printf("Tinh minh cang nong tham cho bao uoc vong trao dang\n");
    printf("Gio trong tim toi, mau hong khong phai phoi\n");
    printf("Xuan qua he toi ta nho nhau luon phuong oi\n");
}
int main(void) {
    loadgraph_1st();
    tarjan();
    loadgraph_2nd();
    findres();
    print();
    return 0;
}