Language: C

/*========================================
	2-sat è§£å³é®é¢ (A1 v A2) ^ (A1 v A3') è¿ç§ åªææ¬å·éæå¤æä¸¤ä¸ªåéçæåèå¼				 																																					
	1ï¼aä¸è½åbä¸èµ·å»ï¼åa->opp(b), b->opp(a)ï¼å°±æ¯è¿ä¸¤æ¡è¾¹ï¼è¯´æaå»ï¼opp(b)ä¸å®å».
	2ï¼äºä»¶Aä¸å®è¦åçè¡¨ç¤ºæ¯ï¼-A->Aï¼è¿æ ·è¡¨ç¤ºå-Aä¸å®è¦åAï¼ä¸2-satåæçç¾ã
	
	1ï¼ç¼©åï¼ç¼©å®åå¤æ­æ¯å¦våvâå¨ä¸ä¸ªå¼ºè¿éåéï¼è¥æ¯ï¼åæ è§£ï¼éåºï¼å¾æ¾ç¶ï¼våvâå¨ä¸ä¸ªåéä¸­è¯´æä¸¤ä¸ªå¿é¡»åæ¶å»ï¼èåä¸è½ï¼çç¾ï¼ï¼
	2: ååè¿è¾¹æé æ°å¾,è¿æ ·éäºå¥åº¦ä¸º0çç¹å°±ç¸å½äºéäºåå¾åºåº¦ä¸º0çç¹ï¼å°±ä¸éè¦å»æåç»§ç¹äºï¼
	3ï¼æææåºï¼æå¥åº¦ï¼
	4ï¼ä»å¥åº¦ä¸º0çç¹å¼å§åï¼åä¸ä¸ªè®°ä¸º1ï¼å°±æå¶oppç¹ä»¥åoppç¹ææç¸è¿çç¹ç»ç»æ è®°ä¸º2ãï¼å¿ç¶æ çç¾ï¼è®ºæå·²è¯æï¼ï¼
=========================================*/
int dfn[V], low[V], stack[V], head[V];
int opp[V], pon[V], bo[V], thead[V];
int indeg[V], tnext[V], tpot[V], Q[V];

int next[E], pot[E], now[E];
bool instack[V];
int tot, n, m, top, num, sign;

void connect(int a,int b)
{
	pot[++tot]=b; next[tot]=head[a]; head[a]=tot;
}
// ç¼©å
void dfs(int v)
{
	dfn[v]=low[v]=++sign; stack[++top]=v; 
	instack[v] = true;
	for (int e=head[v];e!=-1;e=next[e])
	{
		int u=pot[e];
		if ( dfn[u]==0 )
		{
			dfs(u);
			low[v]=min(low[v],low[u]);
		} else
		if (instack[u])
			low[v]=min(low[v],dfn[u]);
	}
	if (low[v]==dfn[v])
	{
		pon[++num] = v;				//è¡¨ç¤ºæ°èç¹çåå½å±ç¹
		do
		{
			int u=stack[top--];
			now[u]=num;
			instack[u]=false;
		}while (stack[top+1]!=v);			
	}		
}
void toposort()
{
	int h=1,t=0;
	for (int i=1;i<=num;i++)
	if (indeg[i] == 0)
		Q[++t] = i;
		
	while (h <= t)
	{
		int v = Q[h++];
		for (int e=thead[v];e!=0;e=tnext[e])
		{
			if (--indeg[tpot[e]] == 0)
				Q[++t] = tpot[e];
		}		
	}
	memset(bo,0,sizeof(bo));
	for (int i=1;i<=t;i++)
	if (bo[Q[i]] == 0)
	{
		bo[Q[i]] = 1;
		bo[now[opp[pon[Q[i]]]]] = 2; //ç±äºå¯¹ç§°æ§ï¼åªéè¦æ è®°ä¸ä¸ªç¹ã
	} 
}
bool 2-sat()
{
	// åç®å¥½oppæ°ç»ï¼æ ¹æ®é¢ç®æ¥è®¾
	n = n * 2;
	for (int i=1;i<=n;i++) 
	if ((i&1)>0) 
		opp[i]=i+1; 
	else 
		opp[i]=i-1;
	// è¿è¾¹ ä¸å¯¹çç¾a->opp[b],b->opp[a],æ¢éaä¸å®è¦éopp[b]
	tot = -1; 
	memset(head,-1,sizeof(head));
	for (int i=1;i<=m;i++) 
	{
		scanf("%d%d",&a,&b);
		connect(a,opp[b]);
		connect(b,opp[a]);
	}
	//ç¼©å
	sign=0; num=0; top=0; 
	memset(dfn,0,sizeof(dfn));
	memset(instack,false,sizeof(instack));	//çè®ºä¸æ¯æ¬¡åå®æ¯ä¸ªç»ç¹é½ä¼åºæ ,æ±ä¿é©
	for (int i=1;i<=n;i++) 
	if (dfn[i]==0) 
		dfs(i);
		
	//çæ¯å¦æè§£ï¼AåAâå¨ä¸ä¸ªç¯ä¸­å°±æ è§£
	for (int i=1;i<=n;i++) 
	if (now[i] == now[opp[i]]) 
		return false;	
	
	// æè§£åååæå¾ï¼æ±è§£
	tot = -1; 
	memset(thead,-1,sizeof(thead));
	memset(indeg,0,sizeof(indeg));
	for (int i=1;i<=n;i++)
	{
		int v = now[i];
		for (int e=head[i];e!=-1;e=next[e])
		if (now[pot[e]] != v)
		{
			int u = now[pot[e]];
			tpot[++tot] = v;
			tnext[tot] = thead[u]; 
			thead[u] = tot;
			indeg[v]++;
		}
	}
	toposort();
	//å¦æ bo[i]==1 è¡¨ç¤ºéè¯¥ç¹
	for (int i=1;i<=n;i++)
		if (bo[now[i]] == 1)
			printf("%d\n",i);
}

Compiler output:
main.c:11:9: error: 'V' undeclared here (not in a function)
   11 | int dfn[V], low[V], stack[V], head[V];
      |         ^
main.c:15:10: error: 'E' undeclared here (not in a function)
   15 | int next[E], pot[E], now[E];
      |          ^
main.c:16:1: error: unknown type name 'bool'
   16 | bool instack[V];
      | ^~~~
main.c:1:1: note: 'bool' is defined in header '<stdbool.h>'; this is probably fixable by adding '#include <stdbool.h>'
  +++ |+#include <stdbool.h>
    1 | /*========================================
main.c: In function 'dfs':
main.c:27:22: error: 'true' undeclared (first use in this function)
   27 |         instack[v] = true;
      |                      ^~~~
main.c:27:22: note: 'true' is defined in header '<stdbool.h>'; this is probably fixable by adding '#include <stdbool.h>'
main.c:27:22: note: each undeclared identifier is reported only once for each function it appears in
main.c:34:32: error: implicit declaration of function 'min' [-Wimplicit-function-declaration]
   34 |                         low[v]=min(low[v],low[u]);
      |                                ^~~
main.c:46:36: error: 'false' undeclared (first use in this function)
   46 |                         instack[u]=false;
      |                                    ^~~~~
main.c:46:36: note: 'false' is defined in header '<stdbool.h>'; this is probably fixable by adding '#include <stdbool.h>'
main.c: In function 'toposort':
main.c:66:9: error: implicit declaration of function 'memset' [-Wimplicit-function-declaration]
   66 |         memset(bo,0,sizeof(bo));
      |         ^~~~~~
main.c:1:1: note: include '<string.h>' or provide a declaration of 'memset'
  +++ |+#include <string.h>
    1 | /*========================================
main.c:66:9: warning: incompatible implicit declaration of built-in function 'memset' [-Wbuiltin-declaration-mismatch]
   66 |         memset(bo,0,sizeof(bo));
      |         ^~~~~~
main.c:66:9: note: include '<string.h>' or provide a declaration of 'memset'
main.c: At top level:
main.c:74:6: error: expected '=', ',', ';', 'asm' or '__attribute__' before numeric constant
   74 | bool 2-sat()
      |      ^