Pagini recente » Cod sursa (job #648979) | Cod sursa (job #2529631) | Cod sursa (job #1259851) | Cod sursa (job #2284673) | Cod sursa (job #3226566)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int nmax = 2e5 + 7;
vector <int> adj[nmax];
vector <int> cc[nmax];
stack<int>s;
int low[nmax], id[nmax], on_stack[nmax];
int curent_id = 0, ssc = 0;
void dfs(int node)
{
curent_id++;
id[node] = curent_id;
s.push(curent_id);
on_stack[curent_id] = 1;
for(auto next:adj[node])
{
if(id[next] == 0)
dfs(next);
if(on_stack[id[next]] == 1)
low[id[node]] = min(low[id[node]], low[id[next]]);
}
if(id[node] == low[id[node]] && on_stack[id[node]] == 1)
{
while(id[node] != s.top())
{
low[s.top()] = id[node];
on_stack[s.top()] = 0;
s.pop();
}
on_stack[s.top()] = 0;
s.pop();
ssc++;
}
}
int main()
{
int n,m,i;
cin >> n >> m;
for(i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
}
for(i = 1; i <= n; i++)
low[i] = i;
for(i = 1; i <= n; i++)
if(id[i] == 0)
dfs(i);
cout << ssc << endl;
for(i = 1; i <= n; i++)
cc[low[id[i]]].push_back(i);
for(i = 1; i < nmax; i++)
{
if(cc[i].size())
{
for(auto it:cc[i])
cout << it << " ";
cout << endl;
}
}
return 0;
}