Cod sursa(job #1561914)

Utilizator Darius15Darius Pop Darius15 Data 4 ianuarie 2016 17:53:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int t,j,s[200001],nr,n,m,i,x,y;
vector <int> v[100001],vt[100001],ct[100001];
bitset <1000001> viz,viz1;
void dfs(int x)
{
  int j;
  t++;viz[x]=true;
  for (j=0;j<v[x].size();j++)
    if (viz[v[x][j]]==false)
    dfs(v[x][j]);
  t++,s[t]=x;
}
void ctc(int x)
{
  int j;
  viz1[x]=true;
  ct[nr].push_back(x);
  for (j=0;j<vt[x].size();j++)
    if (viz1[vt[x][j]]==false)
    ctc(vt[x][j]);
}
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
      f>>x>>y;
      v[x].push_back(y);
      vt[y].push_back(x);
    }
    for (i=1;i<=n;i++)
      if (viz[i]==false)
      dfs(i);
    for (i=t;i>=1;i--)
      if (s[i]!=0)
      if (viz1[s[i]]==false){
      nr++;
      ctc(s[i]);
      }
    g<<nr<<'\n';
    for (i=1;i<=n;i++){
       for (j=0;j<ct[i].size();j++)
    g<<ct[i][j]<<' ';
    g<<'\n';
    }
    return 0;
}