Texte vergleichen

Finde den Unterschied zwischen zwei Textdateien

Live-Editor

Gleiches ausblenden

Zeilenumbruch aus

Ansicht

Vergleichsgenauigkeit

Syntaxhervorhebung

Diffchecker Desktop Der sicherste Weg, Diffchecker zu nutzen. Hol dir die Desktop-App: Deine Diffs verlassen nie deinen Computer!Desktop holen

Untitled diff

Erstellt vor 9 JahrenDiff läuft nie ab

43 Entfernungen

Zeilen
Gesamt
Entfernt

Zeichen
Gesamt
Entfernt

Um diese Funktion weiterhin zu nutzen, aktualisiere auf Diffchecker Pro Preise anzeigen

157 Zeilen

32 Hinzufügungen

Zeilen
Gesamt
Hinzugefügt

Zeichen
Gesamt
Hinzugefügt

Um diese Funktion weiterhin zu nutzen, aktualisiere auf Diffchecker Pro Preise anzeigen

145 Zeilen

#include <cstdio>

#include<bits/stdc++.h>

#include <cstring>

#include <algorithm>

#include <queue>

#include <iostream>

#include <vector>

#include <map>

#include <set>

#define maxn 600009

using namespace std;

int UU[maxn], VV[maxn], WW[maxn], q[maxn];

const int maxn= 600100;

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 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 = UU[G[j]];

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

int v = VV[G[j]];

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

u = findset(u);

v = findset(v);

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

NO[lb] = 1;

}

unset(u, v);

cr.push_back(u);

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

cr.push_back(v);

if(NO[lb])break;

if(NO[lb])

break;

}

for(auto x: cr)

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

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;

p[i]=i;q[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);

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

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

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

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

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

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;

int q;

scanf("%d", &Q);

scanf("%d", &q);

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

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

buf.clear();

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

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[WW[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);

}

//cout << tot << endl;

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++)

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

if(NO[i])

{

if(NO[i]){

puts("NO");

else

}

else{

puts("YES");

}

return 0;

}

Gespeicherte Diffs

Originaltext

Datei öffnen

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#define maxn 600009
using namespace std;
int UU[maxn], VV[maxn], WW[maxn], q[maxn];
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 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 = UU[G[j]];
		int v = VV[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);
		UU[i + 1] = edge[i].u;
		VV[i + 1] = edge[i].v;
		WW[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[WW[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);
	}
	//cout << tot << endl;
	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;
}

Bearbeitung

Datei öffnen

#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;
}