比较文本

查找两个文本文件之间的差异

Real-time diff

Unified diff

Collapse lines

Highlight change

Syntax highlighting

工具

Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Download Diffchecker Desktop Learn more

Untitled diff

Created 7 years agoDiff never expires

113 removals

140 lines

117 additions

145 lines

#include<cstdio>

#include<bits/stdc++.h>

#include<cstring>

using namespace std;

#include<algorithm>

const int maxn= 600100;

#include<queue>

#include<vector>

#include<map>

#include<set>

#define maxn 100009

using namespace std;

int a[maxn], b[maxn], c[maxn], q[maxn];

typedef struct

{

int l,r;

}node;

}node1;

node seg[maxn];

node1 seg[maxn];

typedef struct

{

int u,v,w,id;

}node1;

}node2;

node1 edge[maxn];

node2 edge[maxn];

bool cmp(node1 x,node1 y)

bool cmp(node2 x,node2 y)

{

return x.w<y.w;

}

int p[maxn];

int findset(int x)

{

return x==p[x]?x:p[x]=findset(p[x]);

}

void unionset(int x,int y)

{

p[findset(x)]=findset(y);

}

int vis[maxn];

bool wa[maxn];

set<int>st;

struct Edge

{

int to,id;

};

vector<Edge>G[maxn];

int time;

int dfn[maxn],low[maxn];

int type[maxn];

map<long long,int>mp;

map<int, int>mp;

void dfs(int cur,int fa)

vector< vector<int> > V[maxn];

{

vector<int>tmp[maxn], cr;

vis[cur]=1;

vector<int>buf;

dfn[cur]=low[cur]=++time;

bool NO[maxn];

for(int i=0;i<G[cur].size();i++)

{

int fdset(int x){

int j=G[cur][i].to;

return q[x] == x ? x : q[x] = fdset(q[x]);

if(j!=fa&&vis[j]==1)

}

low[cur]=min(low[cur],dfn[j]);

if(!vis[j])

void unset(int x, int y){

{

q[fdset(x)] = fdset(y);

dfs(j,cur);

}

low[cur]=min(low[cur],low[j]);

if(low[j]>dfn[cur]&&type[G[cur][i].id]==0)

void doit(vector <int> &G){

{

cr.clear();

type[G[cur][i].id]=3;

int lb = G[0];

}

for(int j = 1; j < (int)G.size(); j++){

}

int u = a[G[j]], v = b[G[j]];

}

u = findset(u);v = findset(v);

vis[cur]=2;

if(fdset(u) == fdset(v)){

NO[lb] = 1;

}

unset(u, v);

cr.push_back(u);cr.push_back(v);

if(NO[lb])break;

}

for(auto x: cr)q[x] = x;

}

void check(int x){

for(int i = 0; i < (int)V[x].size(); i++){

doit(V[x][i]);

}

int main()

{

int n,m;

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

for(int i=1;i<=n;i++){

p[i]=i;

p[i]=i;q[i] = i;

for(int i=0;i<m;i++)

}

{

for(int i=0;i<m;i++)

scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);

{

edge[i].id=i+1;

scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);

}

a[i+1] = edge[i].u;

sort(edge,edge+m,cmp);

b[i+1] = edge[i].v;

int cur=0,tot=0;

c[i+1] = edge[i].w;

while(cur<m)

edge[i].id=i+1;

{

}

seg[tot].l=cur;

sort(edge,edge+m,cmp);

while(cur+1<m&&edge[cur].w==edge[cur+1].w)

int cur=0,tot=0;

cur++;

while(cur<m)

seg[tot].r=cur;

{

cur++;tot++;

seg[tot].l=cur;

}

while(cur+1<m&&edge[cur].w==edge[cur+1].w)

for(int i=0;i<tot;i++)

cur++;

{

seg[tot].r=cur;

st.clear();mp.clear();

mp[edge[cur].w] = tot;

for(int j=seg[i].l;j<=seg[i].r;j++)

cur++;tot++;

{

}

Edge e;

int x=findset(edge[j].v);

int q;

int y=findset(edge[j].u);

scanf("%d", &q);

if(x==y)

for(int i = 1; i <= q; i++){

{

buf.clear();buf.push_back(i);

type[edge[j].id]=1;continue;

cr.clear();

}

int num;

else

scanf("%d", &num);

{

for(int j = 0; j < num; j++){

if(x>y)swap(x,y);

int x;

long long num=(long long)x*maxn+y;

scanf("%d", &x);

if(!mp[num]){

int w = mp[c[x]];

mp[num]=edge[j].id;

if((int)tmp[w].size() == 0){

e.to=y;e.id=edge[j].id;

tmp[w].push_back(i);

G[x].push_back(e);

tmp[w].push_back(x);

st.insert(x);

cr.push_back(w);

e.to=x;

}

G[y].push_back(e);

else{

st.insert(y);}

tmp[w].push_back(x);

else

}

{

buf.push_back(x);

type[edge[j].id]=2;

}

type[mp[num]]=2;

for(auto x: cr){

}

V[x].push_back(tmp[x]);

}

tmp[x].clear();

}

set<int>::iterator it;

doit(buf);

time=0;

}

for(it=st.begin();it!=st.end();++it)

for(int i=0;i<tot;i++)

{

if(!vis[*it])dfs(*it,-1);

check(i);

}

for(int j = seg[i].l; j <= seg[i].r; j++){

for(int j=seg[i].l;j<=seg[i].r;j++)

unionset(edge[j].u, edge[j].v);

{

}

if(type[edge[j].id]==0)

}

type[edge[j].id]=2;

for(int i = 1; i <= q; i++)

unionset(edge[j].u,edge[j].v);

}

for(it=st.begin();it!=st.end();++it)

{vis[*it]=0;G[*it].clear();}

}

for(int i=1;i<=m;i++)

{

if(type[i]==1)printf("none\n");

if(NO[i]){

else if(type[i]==2)printf("at least one\n");

puts("NO");

else if(type[i]==3)printf("any\n");

}

else{

puts("YES");

}

return 0;

}

已保存差异

原始文本

Open file

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define maxn 100009
using namespace std;
typedef struct
{
    int l,r;
}node;
node seg[maxn];
typedef struct
{
    int u,v,w,id;
}node1;
node1 edge[maxn];
bool cmp(node1 x,node1 y)
{
    return x.w<y.w;
}
int p[maxn];
int findset(int x)
{
    return x==p[x]?x:p[x]=findset(p[x]);
}
void unionset(int x,int y)
{
   p[findset(x)]=findset(y);
}
int vis[maxn];
bool wa[maxn];
set<int>st;
struct Edge
{
    int to,id;
};
vector<Edge>G[maxn];
int time;
int dfn[maxn],low[maxn];
int type[maxn];
map<long long,int>mp;
void dfs(int cur,int fa)
{
    vis[cur]=1;
    dfn[cur]=low[cur]=++time;
    for(int i=0;i<G[cur].size();i++)
    {
        int j=G[cur][i].to;
        if(j!=fa&&vis[j]==1)
            low[cur]=min(low[cur],dfn[j]);
        if(!vis[j])
        {
            dfs(j,cur);
            low[cur]=min(low[cur],low[j]);
            if(low[j]>dfn[cur]&&type[G[cur][i].id]==0)
            {
                type[G[cur][i].id]=3;
            }
        }
    }
    vis[cur]=2;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        p[i]=i;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        edge[i].id=i+1;
    }
    sort(edge,edge+m,cmp);
    int cur=0,tot=0;
    while(cur<m)
    {
        seg[tot].l=cur;
        while(cur+1<m&&edge[cur].w==edge[cur+1].w)
            cur++;
        seg[tot].r=cur;
        cur++;tot++;
    }
    for(int i=0;i<tot;i++)
    {
        st.clear();mp.clear();
        for(int j=seg[i].l;j<=seg[i].r;j++)
        {
            Edge e;
            int x=findset(edge[j].v);
            int y=findset(edge[j].u);
            if(x==y)
            {
                type[edge[j].id]=1;continue;
            }
            else
            {
                if(x>y)swap(x,y);
                long long num=(long long)x*maxn+y;
                if(!mp[num]){
                mp[num]=edge[j].id;
                e.to=y;e.id=edge[j].id;
                G[x].push_back(e);
                st.insert(x);
                e.to=x;
                G[y].push_back(e);
                st.insert(y);}
                else
                {
                    type[edge[j].id]=2;
                    type[mp[num]]=2;
                }
            }
        }
        set<int>::iterator it;
        time=0;
        for(it=st.begin();it!=st.end();++it)
        {
            if(!vis[*it])dfs(*it,-1);
        }
        for(int j=seg[i].l;j<=seg[i].r;j++)
        {
            if(type[edge[j].id]==0)
                type[edge[j].id]=2;
            unionset(edge[j].u,edge[j].v);
        }
        for(it=st.begin();it!=st.end();++it)
        {vis[*it]=0;G[*it].clear();}
}

for(int i=1;i<=m;i++)
    {
        if(type[i]==1)printf("none\n");
        else if(type[i]==2)printf("at least one\n");
        else if(type[i]==3)printf("any\n");
    }
}

更改后文本

Open file

#include<bits/stdc++.h>
using namespace std;
const int maxn= 600100;
using namespace std;
int a[maxn], b[maxn], c[maxn], q[maxn];
typedef struct
{
	int l,r;
}node1;
node1 seg[maxn];
typedef struct
{
	int u,v,w,id;
}node2;
node2 edge[maxn];
bool cmp(node2 x,node2 y)
{
	return x.w<y.w;
}
int p[maxn];
int findset(int x)
{
	return x==p[x]?x:p[x]=findset(p[x]);
}
void unionset(int x,int y)
{
   p[findset(x)]=findset(y);
}
int vis[maxn];
bool wa[maxn];
set<int>st;
struct Edge
{
	int to,id;
};
vector<Edge>G[maxn];
int type[maxn];
map<int, int>mp;
vector< vector<int> > V[maxn];
vector<int>tmp[maxn], cr;
vector<int>buf;
bool NO[maxn];

int fdset(int x){
	return q[x] == x ? x : q[x] = fdset(q[x]);
}

void unset(int x, int y){
	q[fdset(x)] = fdset(y);
}

void doit(vector <int> &G){
	cr.clear();
	int lb = G[0];
	for(int j = 1; j < (int)G.size(); j++){
		int u = a[G[j]], v = b[G[j]];
		u = findset(u);v = findset(v);
		if(fdset(u) == fdset(v)){
			NO[lb] = 1;
		}
		unset(u, v);
		cr.push_back(u);cr.push_back(v);
		if(NO[lb])break;
	}
	for(auto x: cr)q[x] = x;
}

void check(int x){
	for(int i = 0; i < (int)V[x].size(); i++){
		doit(V[x][i]);
	}
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		p[i]=i;q[i] = i;
	}
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
		a[i+1] = edge[i].u;
		b[i+1] = edge[i].v;
		c[i+1] = edge[i].w;
		edge[i].id=i+1;
	}
	sort(edge,edge+m,cmp);
	int cur=0,tot=0;
	while(cur<m)
	{
		seg[tot].l=cur;
		while(cur+1<m&&edge[cur].w==edge[cur+1].w)
			cur++;
		seg[tot].r=cur;
		mp[edge[cur].w] = tot;
		cur++;tot++;
	}
	
	int q;
	scanf("%d", &q);
	for(int i = 1; i <= q; i++){
		buf.clear();buf.push_back(i);
		cr.clear();
		int num;
		scanf("%d", &num);
		for(int j = 0; j < num; j++){
			int x;
			scanf("%d", &x);
			int w = mp[c[x]];
			if((int)tmp[w].size() == 0){
				tmp[w].push_back(i);
				tmp[w].push_back(x);
				cr.push_back(w);
			}
			else{
				tmp[w].push_back(x);
			}
			buf.push_back(x);
		}
		for(auto x: cr){
			V[x].push_back(tmp[x]);
			tmp[x].clear();
		}
		doit(buf);
	}
	for(int i=0;i<tot;i++)
	{
		check(i);
		for(int j = seg[i].l; j <= seg[i].r; j++){
			unionset(edge[j].u, edge[j].v);
		}
    }	
    for(int i = 1; i <= q; i++)
    {
    	if(NO[i]){
    		puts("NO");
		}   		
    	else{
    		puts("YES");
		}	
	}	
	return 0;
}