Pagini recente » Cod sursa (job #446013) | Cod sursa (job #1413581) | Cod sursa (job #756539) | Cod sursa (job #3235348) | Cod sursa (job #1905586)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MaxN=100005;
int N,M;
vector<int> G[MaxN], c;
vector<vector<int>> cc;
int d[MaxN], low[MaxN];
int deep;
bitset<MaxN> inStack;
stack<int> St;
void Read();
void Tarjan(int x);
int main()
{
Read();
for(int i=1;i<=N;++i)
if(!d[i])
Tarjan(i);
fout<<cc.size()<<'\n';
for(const auto& y : cc)
{
for(const int & x : y)
fout<<x<<" ";
fout<<'\n';
}
return 0;
}
void Read()
{
fin>>N>>M;
while(M--)
{
int x,y;
fin>>x>>y;
G[x].push_back(y);
}
fin.close();
}
void Tarjan(int x)
{
d[x]=low[x]=deep++;
St.push(x);
inStack[x]=true;
for(const int& y : G[x])
{
if(!d[y])
{
Tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(inStack[y])
low[x]=min(low[x],d[y]);
if(d[x]==low[x])
{
c.clear();
int x2;
while(true)
{
c.push_back(x2=St.top());
St.pop();
inStack[x2]=false;
if(x2==x)
break;
}
}
}
cc.push_back(c);
}