Pagini recente » Cod sursa (job #202316) | Cod sursa (job #2158044) | Cod sursa (job #3319994) | Cod sursa (job #3318058) | Cod sursa (job #3336194)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
int nmax = 100000;
vector<int> L[100001], LT[100001], nodes;
vector<int> viz(nmax + 1, 0);
vector<vector<int>> Ctc;
stack<int> q;
void dfs1(int node)
{
viz[node] = 1;
for(auto v: L[node])
{
if(viz[v] == 0)
dfs1(v);
}
q.push(node);
}
void dfs2(int node)
{
viz[node] = 1;
nodes.push_back(node);
for(auto v: LT[node])
{
if(viz[v] == 0)
dfs2(v);
}
}
int main()
{
fin >> n >> m;
int ctc = 0;
for(int i = 1; i <= m; i ++)
{
int x, y;
fin >> x >> y;
L[x].push_back(y);
LT[y].push_back(x);
}
for(int i = 1; i <= n; i ++)
{
if(viz[i] == 0) dfs1(i);
}
for(int i = 1; i <= n; i ++)
viz[i] = 0;
while(!q.empty())
{
int node = q.top();
q.pop();
if(viz[node]) continue;
nodes.clear();
ctc++;
dfs2(node);
Ctc.push_back(nodes);
}
fout << ctc << '\n';
for(auto v: Ctc)
{
for(auto n: v)
fout << n << ' ';
fout << '\n';
}
return 0;
}