Pagini recente » Cod sursa (job #1613390) | Cod sursa (job #2693741) | Cod sursa (job #1123996) | Cod sursa (job #2244495) | Cod sursa (job #2720836)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, nrc;
bool viz[100008], viz2[100008];
vector <int> cc[100008], g[100008], gt[100008];
stack <int> s;
void dfs(int nod)
{
viz[nod] = true;
for(auto it = g[nod].begin(); it != g[nod].end(); ++it)
{
if(!viz[*it])
{
dfs(*it);
}
}
s.push(nod);
}
void dfs2(int nod, int ccc)
{
cc[ccc].push_back(nod);
viz2[nod] = true;
for(auto it = gt[nod].begin(); it != gt[nod].end(); ++it)
{
if(!viz2[*it])
{
dfs2(*it, ccc);
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
int a, b;
cin >> a >> b;
g[a].push_back(b);
gt[b].push_back(a);
}
for(int i = 1; i <= n; ++i)
{
if(!viz[i])
dfs(i);
}
while(!s.empty())
{
int i = s.top();
s.pop();
if(!viz2[i])
dfs2(i, ++nrc);
}
cout << nrc << '\n';
for(int i = 1; i <= nrc; ++i)
{
for(auto it = cc[i].begin(); it != cc[i].end(); ++it)
{
cout << *it << ' ';
}
cout << '\n';
}
return 0;
}