Pagini recente » Cod sursa (job #2117970) | Cod sursa (job #2667833) | Cod sursa (job #1798003) | Cod sursa (job #2815553) | Cod sursa (job #2525923)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100010;
vector<int> graf[NMAX];
int lowlink[NMAX];
int ids[NMAX];
bool inStack[NMAX];
vector<vector<int>> components;
stack<int> stac;
int currentId = 1;
void dfs(int node)
{
stac.push(node);
inStack[node] = true;
ids[node] = currentId++;
lowlink[node] = ids[node];
for(int friendly : graf[node])
{
if(ids[friendly]==0)
dfs(friendly);
if(inStack[friendly])
lowlink[node] = min(lowlink[node], lowlink[friendly]);
}
if(ids[node]==lowlink[node])
{
vector<int> component;
while(stac.top()!=node) {
lowlink[stac.top()]=lowlink[node];
inStack[stac.top()] = false;
component.push_back(stac.top());
stac.pop();
}
component.push_back(stac.top());
inStack[stac.top()] = false;
stac.pop();
components.push_back(component);
}
}
int n, m;
int main()
{
fin>>n>>m;
while(m--)
{
int x, y;
fin>>x>>y;
graf[x].push_back(y);
}
for(int i= 1;i<=n;i++)
{
if(ids[i]==0) dfs(i);
}
fout<<components.size()<<"\n";
for(auto v:components)
{
for(auto x:v)
fout<<x<<" ";
fout<<'\n';
}
return 0;
}