邊的儲存
struct edge
{
int v;
int next;
} edges[maxn*maxn];
int last[maxn];
int tot;
void add(int u,int v)
{
edges[tot].v = v;
edges[tot].next = last[u];
last[u] = tot++;
return ;
}
int dfn[maxn],low[maxn]; //時(shí)間戳 最早能回溯到的祖先位置。
int color[maxn]; //所屬連通分量編號
bool instack[maxn];
int st[maxn],top; //模擬棧
int cnt,scnt; //時(shí)間和連通分量計(jì)數(shù)
Tarjan算法部分：
void tarjan(int u)
{
int x;
dfn[u]=low[u]=cnt++;
st[++top]=u;
instack[u]=1;
for (int j=last[u];j!=-1;j=edges[j].next)
{
int v = edges[j].v;
if (dfn[v]==-1)
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u]) //以u為根節(jié)點(diǎn)的樹形成一個連通分量
{
do
{
x=st[top--];
instack[x]=0;
color[x]=scnt;
}
while (x!=u);
scnt++;
}
return ;
}
solv()函數(shù)部分：
void solve()
{
cnt=0;
scnt=0;
top=0;
memset(dfn,-1,sizeof(dfn));
memset(instack,0,sizeof(instack));
for(int i=0; i<n*2; i++)
if (dfn[i]==-1)
{
tarjan(i);
}
return ;
}
2—SAT中判斷是否形成自環(huán)check()
bool check()
{
for (int i=0; i<n; i++)
if (color[i]==color[i+n])
return 0;
return 1;
}
求出連通分量的解。待定。