Pagini recente » Cod sursa (job #1375209) | Cod sursa (job #431703) | Cod sursa (job #1769587) | Cod sursa (job #2646127) | Cod sursa (job #659734)
Cod sursa(job #659734)
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
bool viz[100002];
int n,m,comp=0,ctc[100002],j;
vector<int>G[100002],GT[100002],v[100002];
stack<int>S;
void CA(int x)
{
viz[x]=1;
for(int i=0;i<G[x].size();i++)
if(!viz[G[x][i]]) CA(G[x][i]);
S.push(x);
}
void CA2(int x)
{
ctc[x]=comp;
for(int i=0;i<GT[x].size();i++)
if(!ctc[GT[x][i]]) CA2(GT[x][i]);
}
int main()
{
int x,y,i;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
fi>>n>>m;
for(i=1;i<=m;i++)
{
fi>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(i=1;i<=n;i++)
if(!viz[i]) CA(i);
while(!S.empty())
{
while(!S.empty() and ctc[S.top()]) S.pop();
if(S.empty()) break;
x=S.top(); S.pop();
comp++;
CA2(x);
}
for(i=1;i<=n;i++)
v[ctc[i]].push_back(i);
fo<<comp<<"\n";
for(i=1;i<=comp;i++)
{
for(j=0;j<v[i].size();j++)
fo<<v[i][j]<<" ";
fo<<"\n";
}
return 0;
}