D40 2-SAT POJ3683 Priest John's Busiest Day

#include<bits/stdc++.h>
using namespace std;

const int N=2005;
int n;
int head[N],to[N*N],ne[N*N],idx;
int dfn[N],low[N],tim,stk[N],top,scc[N],cnt;
int s[N],t[N],d[N];


void add(int a,int b){
  to[++idx]=b,ne[idx]=head[a],head[a]=idx;
}
void tarjan(int x){
  dfn[x]=low[x]=++tim;
  stk[++top]=x;
  for(int i=head[x];i;i=ne[i]){
    int y=to[i];
    if(!dfn[y]){ //若y尚未访问
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if(!scc[y]) //若y已访问且未处理
      low[x]=min(low[x],dfn[y]);
  }
  
  if(low[x]==dfn[x]){ //若x是SCC的根
    ++cnt;
    for(int y=-1;y!=x;)
      scc[y=stk[top--]]=cnt;
  }
}
int main(){
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    int s0,s1,t0,t1,dd;
    scanf("%d:%d %d:%d %d",&s0,&s1,&t0,&t1,&dd);
    s[i]=s0*60+s1;
    t[i]=t0*60+t1;
    d[i]=dd;
  }
  for(int i=0;i<n;i++)
    for(int j=0;j<i;j++){
      if(s[j]+d[j]>s[i]&&s[i]+d[i]>s[j]) 
        add(i,j+n),add(j,i+n); //i,j重叠
      if(t[j]>s[i]&&s[i]+d[i]>t[j]-d[j]) 
        add(i,j),add(j+n,i+n); //i,j+n重叠
      if(s[j]+d[j]>t[i]-d[i]&&t[i]>s[j]) 
        add(i+n,j+n),add(j,i); //i+n,j重叠
      if(t[j]>t[i]-d[i]&&t[i]>t[j]-d[j]) 
        add(i+n,j),add(j+n,i); //i+n,j+n重叠
    }
  
  for(int i=0;i<n*2;i++) if(!dfn[i])tarjan(i);
  for(int i=0;i<n;i++)
    if(scc[i]==scc[i+n]){puts("NO");return 0;}
  puts("YES");
  for(int i=0;i<n;i++){
    if(scc[i]<scc[i+n]) printf("%02d:%02d %02d:%02d\n",
        s[i]/60,s[i]%60,(s[i]+d[i])/60,(s[i]+d[i])%60);
    else printf("%02d:%02d %02d:%02d\n",
        (t[i]-d[i])/60,(t[i]-d[i])%60,t[i]/60,t[i]%60);
  }
}

#include<bits/stdc++.h>
using namespace std;
const int N=4010;
vector<int>G[N];
int s[N], t[N], d[N], tsp, cnt, dfn[N], low[N], scc[N];
stack<int>stk;bool instk[N];
bool check(int a, int b, int c, int d) {return ((a>=c && a<d) || (b>c && b<=d) || (a<=c && b>=d));}
void tarjan(int x)
{
	dfn[x]=low[x]=++tsp; 
	stk.push(x);instk[x]=1;
	for(int y:G[x])
	{
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x], low[y]);
		}
		else if(instk[y]) low[x]=min(low[x], dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		cnt++;
		for(int z=-1;z!=x;)
		{
			z=stk.top();stk.pop();instk[z]=0;
			scc[z]=cnt;
		}
	}
}
int main()
{
	int n; scanf("%d", &n);
	for(int i=1; sh, sm, th, tm; i<=n; i++)
	{
		scanf("%d:%d %d:%d", &sh, &sm, &th, &tm);
		scanf("%d", &d[i]); s[i]=sh*60+sm; t[i]=th*60+tm;
	}
	for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++)
	{
		if(check(s[i], s[i]+d[i], s[j], s[j]+d[j])) G[i].push_back(j+n),G[j].push_back(i+n);
		if(check(s[i], s[i]+d[i], t[j]-d[j], t[j])) G[i].push_back(j), G[j+n].push_back(i+n);
		if(check(t[i]-d[i], t[i], s[j], s[j]+d[j])) G[i+n].push_back(j+n),G[j].push_back(i);
		if(check(t[i]-d[i], t[i], t[j]-d[j], t[j])) G[i+n].push_back(j),G[j+n].push_back(i);
	}

	tsp=cnt=0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low));
	memset(scc, 0, sizeof(scc)); memset(instk, 0, sizeof(instk)); 
	for(int i=1; i<=2*n; i++) if(!dfn[i]) tarjan(i);
	
	for(int i=1; i<=n; i++) if(scc[i]==scc[i+n]) {printf("NO"); return 0;}
	printf("YES\n");
	for(int i=1; x, y; i<=n; i++)
	{
		if(scc[i]<scc[i+n]) x=s[i], y=s[i]+d[i]; 
		else x=t[i]-d[i], y=t[i];
		printf("%02d:%02d %02d:%02d\n", x/60, x%60, y/60, y%60);
	}
	return 0;
}