Cod sursa(job #1445230)

Utilizator Darius15Darius Pop Darius15 Data 30 mai 2015 12:47:34
Problema Componente tare conexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v[100001],vt[100001],sol1[100001];
int n,m,i,x,y,sol[100001],j,l;
bitset <100001> al;
void dfs(int i)
{
  int j;
  for (j=0;j<v[i].size();j++){
     if (sol[v[i][j]]!=l && al[v[i][j]]==false)
      sol[v[i][j]]=l,dfs(v[i][j]);
  }
}
void dft(int i)
{
  int j;
  for (j=0;j<vt[i].size();j++){
     if (sol[vt[i][j]]!=l && al[vt[i][j]]==false){
      if (sol[vt[i][j]]==l-1)
        sol1[l/2].push_back(vt[i][j]),al[vt[i][j]]=true;
      sol[vt[i][j]]=l,dft(vt[i][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 (al[i]==false){
      l++;
      dfs(i);
      l++;
      dft(i);
      }
      g<<l/2<<'\n';
      for (i=1;i<=l/2;i++){
         for (j=0;j<sol1[i].size();j++)
         g<<sol1[i][j]<<' ';
         g<<'\n';
      }

    return 0;
}