Pagini recente » Cod sursa (job #2766875) | Cod sursa (job #751996) | Cod sursa (job #1410388) | Cod sursa (job #760667) | Cod sursa (job #2297965)
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int index = 0;
int lowlink = 0;
public:
void initialize(int x, int y)
{
index = x;
lowlink = y;
}
Node()
{}
Node(int x, int y)
{
initialize(x, y);
}
};
void dfs(int node, int &nr, vector <vector <int>> &ans, stack <int> &stk, vector <Node> &ind, vector <vector <int>> &path)
{
ind[node] = Node(nr, nr);
nr += 1;
stk.push(node);
int vec;
for(unsigned i = 0; i < path[node].size(); i++)
{
vec = path[node][i];
if(ind[vec].index == 0)
dfs(vec, nr, ans, stk, ind, path);
ind[node].lowlink = min(ind[node].lowlink, ind[vec].lowlink);
}
if(ind[node].index != ind[node].lowlink)
return;
vector <int> c;
int now;
while(!stk.empty())
{
now = stk.top();
stk.pop();
c.push_back(now);
if(ind[now].index == ind[now].lowlink)
break;
}
ans.push_back(c);
}
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int main()
{
int n, m;
fin>>n>>m;
vector <vector <int>> ans;
stack <int> stk;
vector <vector <int>> path(n + 1);
vector <Node> ind(n + 1);
int x, y;
for(; m; m--)
{
fin>>x>>y;
path[x].push_back(y);
}
int nr = 1;
for(int i = 1; i <= n; i++)
{
if(ind[i].index == 0)
{
dfs(i, nr, ans, stk, ind, path);
}
}
fout<<ans.size()<<'\n';
for(unsigned i = 0; i < ans.size(); i++)
{
for(unsigned j = 0; j < ans[i].size(); j++)
fout<<ans[i][j]<<' ';
fout<<'\n';
}
return 0;
}