Pagini recente » Borderou de evaluare (job #1093164) | Diferente pentru problema/cbinteractiv intre reviziile 7 si 6 | Borderou de evaluare (job #2655590) | Cod sursa (job #3342655) | Cod sursa (job #3344444)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <bitset>
#define NMax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, sol=0;
vector <int> CTC[NMax];
vector <int> vecini[NMax];
bitset <NMax> v;
stack <int> temp;
vector <int> vecini_t[NMax];
void dfs1(int start)
{
v[start]=1;
for(auto nod: vecini[start])
{
if(v[nod]==0)
dfs1(nod);
}
temp.push(start);
}
void dfs2(int start)
{
v[start]=1;
CTC[sol].push_back(start);
for(auto nod: vecini_t[start])
{
if(v[nod]==0)
dfs2(nod);
}
}
void kasaraju()
{
for(int i=1;i<=n;i++)
{
if(v[i]==0)
dfs1(i);
}
for(int i=1;i<=n;i++)
{
for(auto nod: vecini[i])
{
vecini_t[nod].push_back(i);
}
}
v.reset();
while(!temp.empty())
{
int a=temp.top();
temp.pop();
if(v[a]==0)
{
sol++;
dfs2(a);
}
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
vecini[x].push_back(y);
}
kasaraju();
fout<<sol<<"\n";
for(int i=1;i<=sol;i++)
{
for(auto i: CTC[i])
fout<<i<<" ";
fout<<"\n";
}
return 0;
}