Pagini recente » Cod sursa (job #1161480) | Cod sursa (job #2784187) | Cod sursa (job #2095972) | Cod sursa (job #1777904) | Cod sursa (job #3262266)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 1e5+9;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n,i,j,m,ctc;
vector<int>g[NMAX],gt[NMAX],comp[NMAX],s;
bool viz[NMAX];
void input ();
void dfs1(int node);
void dfs2(int node);
int main()
{
input();
for (i=1; i<=n; i++)
{
if (!viz[i])
{
dfs1 (i);
}
}
for (i=1; i<=n; i++)
{
viz[i]=0;
}
while (!s.empty())
{
int node=s.back();
s.pop_back ();
if (!viz[node])
{
ctc++;
dfs2(node);
}
}
fout<<ctc<<'\n';
for (i=1; i<=ctc; i++)
{
for (auto it : comp[i])
{
fout<<it<<' ';
}
fout<<'\n';
}
return 0;
}
void dfs2(int node)
{
comp[ctc].push_back (node);
viz[node]=1;
for (auto it : gt[node])
{
if (!viz[it])
{
dfs2(it);
}
}
}
void dfs1 (int node)
{
viz[node]=1;
for (auto it : g[node])
{
if (!viz[it])
{
dfs1(it);
}
}
s.push_back (node);
}
void input ()
{
fin>>n>>m;
for (i=1; i<=m; i++)
{
int a,b;
fin>>a>>b;
g[a].push_back (b);
gt[b].push_back (a);
}
}