TOPIC

PROBLEM 1610 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • André Luiz Bittencourt replied 4 years ago

    Galera alguem pode me explicar por que Union-find nao funciona ? Estou recebendo 50 % , minha ideia é que quando um documento depende do outro eu vou uni-los e antes de fazer isso eu verifico se os pais deles sao diferentes por exemplo :

    1 - > 2 (unir 1 com 2) logo o pai de 1 é 2 e o pai de 2 é 2 2 - > 3 (unir 2 com 3) logo o pai de 2 é 3 (por consequencia o pai de 1 vira 3) e o pai de 3 é 3 3 -> 1 (unir 3 com 1) aqui o programa detecta que 3 e 1 possuem o mesmo pai (nesse caso o 3) logo gerou um circulo...

    ele diz que podem haver repetiçoes meu programa cuidou disso tbm...

    Por que a ideia esta errada ?

  • Cristhian Bonilha replied 5 years ago

    wadsom, estude o seguinte caso de teste:

    1
    4 3
    1 2
    3 4
    4 3

    leocij, estude este:

    1
    3 2
    1 2
    3 1

    Pesquise algo sobre deteccão de loop com busca em profundidade.

  • Thiago Magalhaes replied 5 years ago

    Nos casos de teste que colocaram aqui no fórum o meu código passou, mas ele continua dando Wrong answer (10%) . Alguém poderia me ajudar a encontrar o erro ? Fico grato.

    #include <stdio.h>
    
    int g[10001][10001], lbl[10001];
    
    int dfs(int n, int u) {
        lbl[u] = 0;
        int i;
        for(i = 1; i <= n; i++) {
          if (g[u][i] == 1) {
            if(lbl[i] == -1) {
                if(!dfs(n, i)) {
                    return 0;
                }
            } else if(lbl[i] == 0) {
                return 0;
            }
          }
        }
    
        lbl[u] = 1;
        return 1;
    }
    
    void init (int n) {
      int i, j;
      for (i = 1; i <= n; i++)
        lbl[i] = -1;
    
      for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
          g[i][j] = 0;
    }
    
    int main () {
      int t, n, m, a, b, cont, ini;
      scanf("%d", &t);
      while (t--) {
        scanf("%d %d", &n, &m);
        init(n);
        cont = 0;
        while(m--) {
          scanf("%d %d", &a, &b);
          g[a][b] = 1;
          if (cont == 0)
            ini = a;
        }
        if (!dfs(n, ini)) printf("SIM\n");
        else printf("NAO\n");
      }
      return 0;
    }
  • João replied 4 years ago

    E se tiver: 1 -> 2 1 -> 3 2 -> 3

    Seu programa retornaria SIM? O certo é NAO.

  • Cristhian Bonilha replied 5 years ago

    Não usem matriz de adjacência, pois isso vai estourar o limite de memória do código e o URI vai se rejeitar a executar o mesmo. Quando o número de vértices de um grafo for muito grande, procurem usar lista de adjacência.

  • Merli replied 5 years ago

    Tentei fazer com dfs e matriz de adjacencia e deu Wrong Answer (100%). Mudei para lista de adjacencia e deu AC. Fica a dica pra quem esta com duvida.

  • Old man replied 5 years ago

    Bom aparentemente eu corrigi o exercício mas ainda retorna Wrong answer.

    Casos de testes extras que usei:

    5
    8 7
    8 2
    2 3
    3 1
    1 4
    4 6
    6 5
    5 7
    5 4
    5 2
    2 1
    1 4
    4 3
    5 5
    1 4
    4 3
    2 1
    5 2
    4 5
    4 3
    1 2
    3 4
    4 3
    3 2
    1 2
    3 1
    
    R:
    NAO
    NAO
    SIM
    SIM
    NAO
    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    
    using namespace std;
    
    typedef struct Grafos
    {
        int caminho;
        int passei;
    }grafos;
    
    int main()
    {
        int t, i, j, n, m, a, b, semCaminho, sim;
        int venhoDaqui[10000], k;
    
        scanf("%d", &t);
        while(t--)
        {
            scanf("%d %d", &n, &m);
    
            grafos **mat, vet[n+1];
                mat=new grafos*[n+1];
                for(i=0; i<=n; i++)
                    mat[i]=new grafos[n+1];
    
            for(i=1; i<=n; i++)
            {
                for(j=1; j<=n; j++)
                {
                    mat[i][j].caminho=0;
                }
                vet[i].passei=0;
            }
    
            while(m--)
            {
                scanf("%d %d", &a, &b);
                    mat[a][b].caminho=1;
            }
    
            i=1; k=0; venhoDaqui[k]=0, sim=0;
    
            while(i<=n)
            {
                j=1;
                while(j<=n)
                {
                    semCaminho=0;
                    if(mat[i][j].caminho==1)
                    {
                        if(vet[j].passei==1)
                        {
                            printf("SIM\n");
                            sim=1;
                            venhoDaqui[k]=0;
                            i=n;
                            break;
                        }
                        else
                        {
                            vet[i].passei=1;
                            k++;
                            venhoDaqui[k]=i;
                            i=j; j=1;
                            semCaminho=1;
                        }
                    }
                    else
                    {
                        j++;
                    }
                }
    
                if(semCaminho==0)
                {
                    if(venhoDaqui[k]==0)
                    {
                        i++;
                    }
                    else
                    {
                        mat[venhoDaqui[k]][i].caminho=0;
                        vet[venhoDaqui[k]].passei=0;
                        i=venhoDaqui[k];
                        k--;
                    }
                }
                else
                {
                    if(venhoDaqui[k]==0)
                        i++;
                }
            }
    
            if(sim==0)
                printf("NAO\n");
        }
    
        return 0;
    }
  • Francisco Thiesen replied 4 years ago

    Estou tomando 10% WA, mas não consigo achar meu erro..

    #include <cmath>
    #include <climits>
    #include <queue>
    #include <vector>
    #include <map>
    #include <cstdio>
    #include <cstdlib>
    #include <fstream>
    #include <iomanip>   
    #include <iostream>  
    #include <sstream>  // istringstream buffer(myString);
    #include <stack>
    #include <algorithm>
    #include <cstring>
    #include <cassert>
    #include <set>
    #include <unordered_map>
    #include <unordered_set>
    #include <string>
    #include <bitset>
    using namespace std;
    #define F(i,L,R) for (int i = L; i < R; i++) //next four are for "for loops"
    #define FE(i,L,R) for (int i = L; i <= R; i++)
    #define FF(i,L,R) for (int i = L; i > R; i--)
    #define FFE(i,L,R) for (int i = L; i >= R; i--)
    #define getI(a) scanf("%d", &a) //next three are handy ways to get ints, it's also force you to use '&' sign
    #define getII(a,b) scanf("%d%d", &a, &b)
    #define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
    //for map, pair
    #define mp make_pair
    #define fi first
    #define se second
    // for debug
    #define MAXN 10010
    //for vectors
    #define pb push_back
    typedef int elem_t;
    typedef vector<int> vi; 
    typedef vector<vi> vvi; 
    typedef pair<int,int> ii; 
    
    vvi AdjList(MAXN);
    bitset<MAXN> visited;
    bitset<MAXN> recurStack;
    bool cycleFind(int v)
    {
        if(visited[v] == false)
        {
            visited[v] = true;
            recurStack[v] = true;
            F(i,0,AdjList[v].size())
            {
                if(!visited[AdjList[v][i]] && cycleFind(AdjList[v][i]))
                    return true;
                else if(recurStack[AdjList[v][i]] == true)
                    return true;
            }
        }
        recurStack[v] = false;
        return false;
    }
    
    int main()
    {
        int t;
        getI(t);
        while(t--)
        {
            int a, b;
            getII(a,b);
            F(i,0,b)
            {
                int x, y;
                getII(x,y);
                AdjList[x].pb(y);
            }
            bool cyc = false;
            FE(i,1,a)
            {
                cyc = cycleFind(a);
                if(cyc)break;
            }
            if(!cyc)
                cout << "NAO" << endl;
            else
                cout << "SIM" << endl;
    
            recurStack.reset();
            visited.reset();
            F(i,0,AdjList.size())
                AdjList[i].clear();
        }
        return 0;
    
    }
  • marcospqf replied 5 years ago

    Galera acabei de passar! pra quem está agarrado, eu estava tomando wrong answer 100% sendo que o problema do meu código era time limit! Tentem implementar DFS representando o grafo como lista de adjacências que passa

  • Walisson Pereira replied 5 years ago

    Uma dica para quem está com dificuldade. Ordenação topológica resolve o problema.

  • Mateus Coutinho Marim replied 5 years ago

    Meu código está dando Runtime Error, alguém sabe me dizer o porque? Até agora todos casos de teste que tentei deram certo.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #define fori(i, n) for(int i = 0; i < (n); i++)
    #define forj(j, n) for(int j = 0; j < (n); j++)
    
    using namespace std;
    
    struct Vertex{
        int v;
        bool visited;
        vector<int> adj;
        Vertex(){
            visited = false;
        }
    };
    
    void addEdge(vector<Vertex> &g, int a, int b){
        g[a-1].v = a;   
        g[b-1].v = b;
        g[a-1].adj.push_back(b);
    }
    
    void DFS_VISIT(vector<Vertex> &V,Vertex u, int &time, bool *recurStack, bool &findCycle){
        time++;     
        if(findCycle)
            return ; 
        V[u.v-1].visited = true;
        recurStack[u.v-1] = true;
        for(int v:u.adj){
            if(recurStack[v-1]){
                findCycle = true;
            }else if(!V[v-1].visited){
                DFS_VISIT(V,V[v-1], time, recurStack, findCycle);
            }
        }   
        recurStack[u.v-1] = false;
    }
    
    bool DFS(vector<Vertex> &V){
        int time = 0;
        bool recurStack[V.size()], findCycle = false;
    
        fori(i, V.size()){
            recurStack[i] = false;
        }
        for(int i = 0; i < V.size(); i++){
            if(!V[i].visited)
                DFS_VISIT(V, V[i], time, recurStack, findCycle);
            if(findCycle)
                return findCycle;
        }
        return false;
    }
    
    int main(){
        int T, N, M, A, B;
    
        cin >> T;
    
        while(T != 0 && T--){
            cin >> N >> M;
            vector<Vertex> V(N);
            fori(i, M){
                cin >> A >> B;
                addEdge(V, A, B);
            }   
            if(DFS(V)){
                cout << "SIM" << endl;
            }else
                cout << "NAO" << endl;
        }
    }
  • Albert Mourato replied 5 years ago

    #include <bits/stdc++.h>
    using namespace std;
    int matriz[10000][10000];
    int main(){
        //freopen("in.txt", "r", stdin);
        int k=0,t=0, m=0, n=0, a=0, b=0, aux = 0;
        cin>>t;
        while(t>0){
            k = 0;
            aux = 0;
            cin>>n>>m;
            while(k<m){
                    //adicionar ao grafo
                    cin>>a>>b;
                    if(aux<a){
                        aux = a;
                    }
                    matriz[a][b] = 1;
                    k++;
            }
                for(int i = 0; i<=aux;i++){
                    for(int j = 0 ; j<=n;j++){
                            if(matriz[i][j]==1&&matriz[j][i]==0){
                                int v = 0;
                                while(v<=n){
                                    if(matriz[j][v]==1){
                                        matriz[i][v]=1;
                                    }
                                    v++;
                                }
                            }else if(matriz[j][i]==1&&matriz[i][j]==0){
                                int v = 0;
                                while(v<=n){
                                    if(matriz[i][v]==1){
                                        matriz[j][v]=1;
                                    }
                                    v++;
                                }
                            }
                    }
                }
                bool auxx = true;
                for(int i = 0; i<=aux;i++){
                    for(int j = 0 ; j<=n;j++){
                        if(matriz[i][j]+matriz[j][i]>1){
                            cout<<"SIM\n";
                            i = aux+1;
                            j = n+1;
                            auxx = false;
                        }
                    }
                }
    
                if(auxx){
                    cout<<"NAO\n";
                }
                memset(matriz, 0, sizeof(matriz));
                t--;
            }
    }

    Alguém sabe dizer porque recebo 100% de wa? Todos os casos que eu ja testei estavam corretos

  • João Antonio replied 5 years ago

    Alguém sabe o que há de errado com o código? Funcionou em todos os casos, mas, mesmo assim, estou tomando WA

    include include include define Vertex int define maxV 100

    static int time, prnt[maxV], d[maxV], f[maxV];

    static int lbl[maxV];

    typedef struct node* link;

    struct node { Vertex w; link next; };

    struct digraph { int V; int A; link* adj; };

    typedef struct digraph* Digraph;

    link NEW (Vertex v, link next) { link x = (link)malloc(sizeof x);

    x->w = v; x->next = next;

    return x; }

    define graph digraph define Graph Digraph

    Digraph DIGRAPHinit (int V) { Vertex v;

    Digraph g = (Digraph)malloc(sizeof *g);

    g->V = V; g->A = 0;

    g->adj = (link)malloc(Vsizeof(link)); for (v = 0; v < g->V; v++) g->adj[v] = NULL;

    return g; }

    void DIGRAPHinsertA(Digraph g, Vertex v, Vertex w) { link p;

    if (v == w) return;

    for (p = (link)g->adj[v]; p != NULL; p = p->next) if (p->w == w) return;

    g->adj[v] = NEW(w, g->adj[v]);

    g->A++; }//

    define GRAPHinit DIGRAPHinit define GRAPHshow DIGRAPHshow

    void DIGRAPHdestroy (Digraph g) { Vertex v; link p, q; for (v = 0; v < g->V; v++) { p = g->adj[v]; while (p) { q = p->next; free(p); g->A--; p = q; } } free(g); }

    int cycleR (Digraph g, Vertex v) { link p; d[v] = time++;

    for (p=g->adj[v]; p; p = p->next)
        if (d[p->w] == -1) {
            prnt[p->w] = p->w;
            if (cycleR(g, p->w) == 1) return 1;
        }
        else if (f[p->w] == -1) return 1;
        f[v] = time++;
        return 0;

    }

    int DIGRAPHcycle (Digraph g) {

    Vertex v;
    time  = 0;
    
    for (v = 0; v< g->V; v++) {
        d[v] = f[v] = -1;
        prnt[v] = -1;
    }
    for (v = 0; v< g->V; v++) 
        if (d[v] == -1)
            if (cycleR(g, v) == 1) 
               return 1;
    
    return 0;

    }

    int main () {

    int t, m, n, i, a, b, j;
    
    scanf ("%d", &t);
    
    Digraph g;
    
    int *casos = (int*) malloc (sizeof (int) * t);
    int flag = 0;
    
    for (j = 0; j < t; j++) {
        do {
            scanf ("%d %d", &n, &m);
    
        } while ((n < 2 || n > 100) || m < 1 || m > 300);
    
        g = DIGRAPHinit (n);
    
        for (i = 0; i < m; i++) {
             flag = 0;
             scanf ("%d %d", &a, &b);
             a--;
             b--;
            if ((a != b) && (a >= 0) && (b < n))
                DIGRAPHinsertA(g, a, b);
            else{
                flag  =1;
                casos[j] = 0;
                break;      
            }
        }
    
        if (!flag)
            casos[j] = DIGRAPHcycle(g);
        DIGRAPHdestroy(g);
    }   
    
    for (j = 0; j  < t; j++)
        if (casos[j] == 1)
            printf("SIM\n");
        else
            printf ("NAO\n");
    
    free(casos);
    
    return 0;

    }

  • Jeremias Moreira Gomes replied 5 years ago

    Testei diversos casos e continuo recebendo WA em 10%. Se alguém puder me citar algum caso em que dê errado, agradeço.

    #include <stdio.h>
    
    #define N 10001
    #define BRANCO 0
    #define CINZA -1
    #define PRETO 1
    
    int G[N][N];
    int cor[N];
    
    void zera(int n);
    
    int dfs(int u, int n);
    
    int main()
    {
        int t;
        int n, m;
        int a, b;
        int i;
        int ori;
        scanf("%d", &t);
        while(t--) {
            scanf("%d %d", &n, &m);
            zera(n);
            for(i = 0; i < m; i = i + 1) {
                scanf("%d %d", &a, &b);
                G[a][b] = 1;
                if(!i) {
                    ori = a;
                }
            }
            if(dfs(a, n)) {
                printf("NAO\n");
            } else {
                printf("SIM\n");
            }
        }
    }
    
    void zera(int n)
    {
        int i, j;
        for(i = 1; i <= n; i = i + 1) {
            for(j = 1; j <= n; j = j + 1) {
                G[i][j] = 0;
            }
            cor[i] = BRANCO;
        }
    }
    
    int dfs(int u, int n)
    {
        int v;
        cor[u] = CINZA;
        for(v = 1; v <= n; v = v + 1) {
            if(G[u][v] != 0) {
                if(cor[v] == BRANCO) {
                    if(!dfs(v, n)) {
                        return 0;
                    }
                } else if(cor[v] == CINZA) {
                    return 0;
                }
            }
        }
        cor[u] = PRETO;
        return 1;
    }
  • cavalca replied 5 years ago

    boa noite, alguem pode me ajudar? testei o programa no meu pc e no toolkit, porem estou recebendo wa 100%

    include

    int main() {

    int t, n, m, a, b, v[999999], i, j;
    while(scanf("%d", &t) != EOF){
        for(i=0;i<100000;i++) v[i]=0;
        scanf("%d %d", &n, &m);
        for(j=0;j<m;j++){
            scanf("%d %d", &a, &b);
            v[a]=v[a]+1;
            v[b]=v[b]+1;
            if(v[a]==2) v[0]=1;
        }
        if(v[0]==1) printf("SIM\n");
        else printf("NAO\n");
    }
    
    return 0;

    }

  • Bruno Otávio replied 5 years ago

    Engraçado, estou tomando WA 50% mas está batendo com todos os casos que vi aqui e que testei em casa... Alguém tem uma ideia de onde pode estar dando errado?

    #include <bits/stdc++.h>
    using namespace std;
    
    vector<int> arestas[10001];
    int Visitados [10001];
    int vertices, aresta;
    int ciclo;
    
    void dfs (int v)
    {
        for (int i=0; i<(arestas[v].size()); i++)
        {
            if (!Visitados[arestas[v][i]])
            {
                Visitados[v] = true;
                dfs(arestas[v][i]);
            }
            else
            {
                ciclo = 1;
            }
        }
    }
    
    int main()
    {
        ios::sync_with_stdio(0);
    
        int n_casos;
        cin >> n_casos;
        for (int i=0; i<n_casos; i++)
        {
            cin >> vertices >> aresta;
    
            for (int j=0; j<aresta; j++)
            {
                int origem, destino;
                cin >> origem >> destino;
    
                arestas[origem].push_back(destino);
            }
    
            ciclo = 0;
            for (int k=1; k<=vertices; k++)
            {
                for (int j=1; j<=vertices; j++)
                    Visitados[j] = false;
                dfs(k);
                if (ciclo)
                    break;
            }
    
            if (!ciclo)
                cout << "NAO\n";
            else
                cout << "SIM\n";
    
            for (int j=1; j<=vertices; j++)
                arestas[j].clear();
        }
    
       return 0;
    }
  • Weuler Borges replied 5 years ago

    Meu código funcionou em todos os casos que consegui pensar e PARECE estar certo! Entretando, recebo 100% WA! Será que alguém consegue ver algo que não estou vendo?

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int adj[10002][10002];
    int status[10002];
    int vertices, bordas;
    
    bool dfs (int no) {
        bool ciclo=false;
        status[no] = 1;
    
        for (int i=0;i<vertices;i++) {
            if (adj[no][i] == 1) {
                if (status[i] == 1) {
                    ciclo=true;
                } else
                    if (status[i] == 0) {
                        ciclo |= dfs(i);
                    }
            }
        }
    
        status[no] = 2;
        return ciclo;
    
    }
    
    int main () {
    
        int t;
    
        cin >> t;
    
        while (t--) {
            cin >> vertices >> bordas;
    
            for (int i=0;i<vertices;i++) {
                for (int j=0;j<vertices;j++) {
                    adj[i][j] = 0;
                }
            }
            for (int i=0;i<vertices;i++) status[i] = 0;
    
            for (int k=0;k<bordas;k++) {
                int a, b;
                cin >> a >> b;
    
                adj[a-1][b-1] = 1;
            }
            bool res=false;
            for (int i=0;i<vertices;i++) {
                for (int j=0;j<vertices;j++) {
                    if (adj[i][j] == 1 && status[i] == 0)
                        res |= dfs(i);
                }
            }
    
            if (res) cout << "SIM" << endl;
            else cout << "NAO" << endl;
        }
    
    }
  • Wadson Barbosa replied 5 years ago

    obrigado Cristhian, estava esquecendo de verificar isso.

  • Old man replied 5 years ago

    Alguém pode dar uma forcinha? Deu Wrong answer, mas os testes passaram.

    Obrigado Cristhian, vou pesquisar a respeito.
  • Wadson Barbosa replied 5 years ago

    olá pessoal, alguém poderia me ajudar? estou levando 10% WA..

    #include <stdio.h>
    #include <stdlib.h>
    
    #define BRANCO 0
    #define CINZA -1
    #define PRETO 1
    
    typedef struct{
    
        int **matriz;
        int *grau;
        int nvertices;
        int *cor;
    
    } grafo;
    
    grafo g;
    
    void init_G()
    {
    
        int i;
        g.matriz=malloc((31000)*sizeof(int));
        g.grau=malloc((31000)*sizeof(int));
        g.cor=malloc((31000)*sizeof(int));
        for(i=0;i<31000;i++)g.matriz[i]=malloc((31000)*sizeof(int));
    }
    
    void init_grafo(int m){
    
        g.nvertices = 0;
        int i;
        for( i = 0; i <m; i++)
            {
                g.grau[i] =0;
                g.cor[i] = 0;
            }
    
    }
    
    int dfs(int u) {
        g.cor[u] = CINZA;
        int i;
        for( i=0; i<g.grau[u]; i++) {
            int v = g.matriz[u][i];
            if(g.cor[v] == BRANCO) {
                if(!dfs(v)) {
                    return 0;
                }
            } else if(g.cor[v] == CINZA) {
                return 0;
            }
        }
    
        g.cor[u] = PRETO;
        return 1;
    }
    
    int main(){
    
        int x, y, m,i,vezes;
    
        init_G();
        init_grafo(31000);
        scanf("%d",&vezes);
    
        while(vezes--){
    
        scanf("%d %d", &g.nvertices, &m);
    
        int inicio;
        for(i = 0; i <m; i++){
            scanf("%d %d", &x, &y);
            if(i==0)
            inicio=x-1;
            g.matriz[x-1][g.grau[x-1]++] = y-1;
    
        }
        if(!dfs(inicio))printf("SIM\n");
        else printf("NAO\n");
        init_grafo(g.nvertices+2);
        }
    
        return 0;
    }
1 of 2