Pagini recente » Cod sursa (job #983335) | Cod sursa (job #976581) | Cod sursa (job #3352402) | Monitorul de evaluare | Cod sursa (job #3336052)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, th_time;
const int N = 100007;
vector<int> a[N], disc(N, 0), l_link(N, 0), still_open(N, 0);
map<int, vector<int>> comp;
int ct_comp;
stack<int> nodes;
void DFS(int x)
{
l_link[x] = disc[x] = ++th_time;
still_open[x] = 1;
nodes.push(x);
for(auto y: a[x])
{
if(!disc[y])
DFS(y);
if(still_open[y])
l_link[x] = min(l_link[x], l_link[y]);
}
if(l_link[x] == disc[x])
{
ct_comp++;
while(nodes.top() != x)
{
comp[ct_comp].push_back(nodes.top());
nodes.pop();
}
comp[ct_comp].push_back(nodes.top());
nodes.pop();
}
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
a[x].push_back(y);
}
for(int i = 1; i <= n; i++)
if(!disc[i])
DFS(i);
fout << comp.size() << "\n";
for(auto w: comp)
{
for(auto x: w.second)
fout << x << " ";
fout << "\n";
}
return 0;
}