Pagini recente » Cod sursa (job #226167) | Cod sursa (job #2637106) | Cod sursa (job #882091) | Cod sursa (job #1794781) | Cod sursa (job #2206707)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,i,j,a,b,id,rz,f[100005],low[100005];
vector<int> vec[100005];
deque<int> q;
vector<int> cmp[100005];
void tarjan(int x)
{
q.push_back(x);
low[x]=id;
f[x]=id++;
for(int i=0;i<vec[x].size();i++)
{
if(f[vec[x][i]]==0)
tarjan(vec[x][i]);
low[x]=min(low[x],low[vec[x][i]]);
}
if(low[x]==f[x])
{
rz++;
while(!q.empty()&&f[q.back()]>=f[x])
{
cmp[rz].push_back(q.back());
q.pop_back();
}
}
}
int main() {
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>a>>b;
vec[a].push_back(b);
}
id=1;
for(i=1;i<=n;i++)
if(f[i]==0)
{
tarjan(i);
}
fout<<rz<<"\n";
for(i=1;i<=rz;i++)
{
for(j=0;j<cmp[i].size();j++)
fout<<cmp[i][j]<<" ";
fout<<"\n";
}
}