0709_11838_come_and_go.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyML5Ta/WGZ/Zwh1WP0OB7sc",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lmcanavals/acomplex/blob/main/0709_11838_come_and_go.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# [11838 Come and Go](https://onlinejudge.org/external/118/11838.pdf)"
      ],
      "metadata": {
        "id": "mJ2YD6YGSANG"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "FXg4Shr-3lFx",
        "outputId": "a319554c-6f8c-45a1-9c98-a954afdc57a0"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Overwriting 1.in\n"
          ]
        }
      ],
      "source": [
        "%%file 1.in\n",
        "4 5\n",
        "1 2 1\n",
        "1 3 2\n",
        "2 4 1\n",
        "3 4 1\n",
        "4 1 2\n",
        "3 2\n",
        "1 2 2\n",
        "1 3 2\n",
        "3 2\n",
        "1 2 2\n",
        "1 3 1\n",
        "4 2\n",
        "1 2 2\n",
        "3 4 2\n",
        "0 0"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def reverseGraph(G):\n",
        "  n = len(G)\n",
        "  Grev = [[] for _ in range(n)]\n",
        "\n",
        "  for u in range(n):\n",
        "    for v in G[u]:\n",
        "      Grev[v].append(u)\n",
        "\n",
        "  return Grev"
      ],
      "metadata": {
        "id": "MZF0B0Nl5VLD"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def dfs(G, u, lst, visited):\n",
        "  visited[u] = True\n",
        "  for v in G[u]:\n",
        "    if not visited[v]:\n",
        "      dfs(G, v, lst, visited)\n",
        "\n",
        "  lst.append(u)"
      ],
      "metadata": {
        "id": "DUtqooA65RrB"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def kosaraju(G):\n",
        "  n = len(G)\n",
        "  visited = [False]*n\n",
        "  f = []\n",
        "\n",
        "  Grev = reverseGraph(G)            # step 1\n",
        "\n",
        "  for u in range(n):                # step 2\n",
        "    if not visited[u]:\n",
        "      dfs(Grev, u, f, visited)\n",
        "\n",
        "  visited = [False]*n               # step 3\n",
        "  scc = []\n",
        "  for u in reversed(f):\n",
        "    if not visited[u]:\n",
        "      cc = []\n",
        "      dfs(G, u, cc, visited)\n",
        "      scc.append(cc)\n",
        "\n",
        "  return scc"
      ],
      "metadata": {
        "id": "jsrqrGPk5QNr"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "f = open(\"1.in\")\n",
        "def input():\n",
        "    return f.readline().strip()\n",
        "\n",
        "def read():\n",
        "    return map(int, input().split())\n",
        "\n",
        "N, M = read()\n",
        "while N != 0:\n",
        "    G = [[] for _ in range(N)]\n",
        "    for _ in range(M):\n",
        "        V, W, P = read()\n",
        "        V -= 1\n",
        "        W -= 1\n",
        "        G[V].append(W)\n",
        "        if P == 2:\n",
        "            G[W].append(V)\n",
        "\n",
        "    scc = kosaraju(G)\n",
        "    print(1 if len(scc) == 1 else 0)\n",
        "\n",
        "    N, M = read()\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fsRJgU5n3wkS",
        "outputId": "ed45d46b-87c7-4b07-f77b-6a13636ccb02"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1\n",
            "1\n",
            "0\n",
            "0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "LLc7GamK5duD"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}